The classical problem of the lid-driven cavity extended infinitely in the spanwise direction is considered for non-Newtonian shear-thinning and shear-thickening fluids, where the viscosity is modeled by the Carreau model. Linear stability is used to determine the critical Reynolds number at which the two-dimensional base-flow becomes unstable to three-dimensional spanwise-periodic disturbances. We consider a square cavity, characterized by steady unstable modes, and a shallow cavity of aspect ratio 0.25, where oscillating modes are the first to become unstable for Newtonian fluids. In both cases, the critical Reynolds number first decreases with decreasing power-index n (from shear-thickening to shear-thinning fluids) and then increase again for highly pseudoplastic fluids. In the latter case, this is explained by the thinner boundary layers at the cavity walls and less intense vorticity inside the domain. Interestingly, oscillating modes are found at critical conditions for shear-thickening fluids in a square cavity while the shallow cavity supports a new instability of lower frequency for large enough shear-thinning. Analysis of kinetic energy budgets and structural sensitivity are employed to investigate the physical mechanisms behind the instability. (C) 2012 Elsevier B.V. All rights reserved.