We consider the stability of a multi-layer plane Poiseuille flow of two Bingham fluids. It is shown that this two-fluid flow is frequently more stable than the equivalent flow of either fluid alone. This phenomenon of super-stability results only when the yield stress of the fluid next to the channel wall is larger than that of the fluid in the centre of the channel, which need not have a yield stress. Our result is in direct contrast to the stability of analogous flows of purely viscous generalised Newtonian fluids, for which short wavelength interfacial instabilities can be found at relatively low Reynolds numbers. The results imply the existence of parameter regimes where visco-plastic lubrication is possible, permitting transport of an inelastic generalised Newtonian fluid in the centre of a channel, lubricated at the walls by a visco-plastic fluid, travelling in a stable laminar flow at higher flow rates than would be possible for the single fluid alone.