The first realization of instabilities in the shear flow between two superfluids is examined. The interface separating the A and B phases of superfluid 3He is magnetically stabilized. With uniform rotation we create a state with discontinuous tangential velocities at the interface, supported by the difference in quantized vorticity in the two phases. This state remains stable and nondissipative to high relative velocities, but finally undergoes an instability when an interfacial mode is excited and some vortices cross the phase boundary. The measured properties of the instability are consistent with the classic Kelvin-Helmholtz theory when modified for two-fluid hydrodynamics.