In this paper we present the linear stability analysis of the interface between two non-Newtonian inelastic fluids in a straight channel driven by a pressure gradient. Two theological models of non-Newtonian behavior are studied: (a) Bingham-like fluids and (b) Carreau-Yasuda fluids. For each theological model, the linearized equations describing the evolution of small two-dimensional disturbances are derived and the stability problem is formulated as an eigenvalue problem for a set of ordinary differential equations of the Orr-Sommerfeld type. Discretization is performed using a pseudospectral technique based on Chebyshev polynomial expansions. The resulting generalized matrix eigenvalue problem is solved using the QZ algorithm. The results on the onset of instability are presented in the form of stability maps for a range of zero-shear-rate viscosity ratios, thickness ratios, power-law constants, material time constants, Yasuda constants, apparent yield stresses and stress growth exponents. Increasing the stress growth exponents or apparent yield stresses of the viscoplastic fluids has a stabilizing effect on the interface. For shear thinning fluids, increasing the zero-shear-rate viscosity ratio or shear thinning of the fluids destabilizes the interface. The effect of other parameters can be stabilizing or destabilizing depending on the flow configuration and wavelength.