Interfaces between immiscible polymer melts can exhibit significant slip when subjected to large shear stresses. We describe and analyze a slip-link/tube model of the nonlinear steady-state rheology of an interface between entangled immiscible polymer melts. The model assumes that near equilibrium shear stress is transmitted across such an interface primarily by chains that form loops across the interface and entangle with chains of the other species. Such binary interfacial entanglements can be created by diffusion of chain ends to the interface and destroyed by either Brownian reptation or slip-induced convective constraint release. Interfacial stress is predicted to be a nonmonotonic function of interfacial slip velocity, leading to the possibility of a stick-slip transition between an entangled state with a very low slip velocity and an unentangled state with a much higher slip velocity.