The three-dimensional linear stability characteristics of pressure-driven two-layer channel flow are considered, wherein a Newtonian fluid layer overlies a layer of a Herschel-Bulkley fluid. We focus on the parameter ranges for which Squire's theorem for the two-layer Newtonian problem does not exist. The modified Orr-Sommerfeld and Squire equations in each layer are derived and solved using an efficient spectral collocation method. Our results demonstrate the presence of three-dimensional instabilities for situations where the square root of the viscosity ratio is larger than the thickness ratio of the two layers; these "interfacial" mode instabilities are also present when density stratification is destabilizing. These results may be of particular interest to researchers studying the transient growth and nonlinear stability of two-fluid non-Newtonian flows. We also show that the "shear" modes, which are present at sufficiently large Reynolds numbers, are most unstable to two-dimensional disturbances. © 2010 American Institute of Physics.