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 shal- low 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 aga...