We consider, for the first time, the stability of the non-Newtonian boundary layer flow over a flat plate. Shear-thinning and shear-thickening flows are modelled using a Carreau constitutive viscosity relationship. The boundary layer equations are solved in a self-similar fashion. A linear asymptotic stability analysis, that concerns the lower-branch structure of the neutral curve, is presented in the limit of large Reynolds number. It is shown that the lower-branch mode is destabilised and stabilised for shear-thinning and shear-thickening fluids, respectively. Favourable agreement is obtained between these asymptotic predictions and numerical results obtained from an equivalent Orr-Sommerfeld type analysis. Our results indicate that an increase in shear-thinning has the effect of significantly reducing the value of the critical Reynolds number, this suggests that the onset of instability will be significantly advanced in this case. This postulation, that shear-thinning destabilises the boundary layer flow, is further supported by our calculations regarding the development of the streamwise eigenfunctions and the relative magnitude of the temporal growth rates.