We derive a flat-interface model to describe the flow of two horizontal, stably stratified fluids, where the bottom layer exhibits non-Newtonian rheology. The model takes into account the yield stress and power-law nature of the bottom fluid. In the light of the large viscosity contrast assumed to exist across the fluid interface, and for large pressure drops in the streamwise direction, the possibility for the upper Newtonian layer to display fully developed turbulence must be considered, and is described in our model. We develop a linear-stability analysis to predict the conditions under which the flat-interface state becomes unstable, and pay particular attention to characterizing the influence of the non-Newtonian rheology on the instability. Increasing the yield stress (up to the point where unyielded regions form in the bottom layer) is destabilizing; increasing the flow index, while bringing a broader spectrum of modes into play, is stabilizing. In addition, a second mode of instability is found, which depends on conditions in the bottom layer. For shear-thinning fluids, this second mode becomes more unstable, and yet more bottom-layer modes can become unstable for a suitable reduction in the flow index. One further difference between the Newtonian and non-Newtonian cases is the development of unyielded regions in the bottom layer, as the linear wave on the interface grows in time. These unyielded regions form in the trough of the wave, and can be observed in the linear analysis for a suitable parameter choice. (c) 2010 Elsevier B.V. All rights reserved.