We theoretically illustrate how complex fluids flowing over superhydrophobic surfaces may exhibit giant flow enhancements in the double limit of small solid fractions (𝜀≪1) and strong shear thinning (𝛽≪1, 𝛽 being the ratio of the viscosity at infinite shear rate to that at zero shear rate). Considering a Carreau liquid within the canonical scenario of longitudinal shear-driven flow over a grooved superhydrophobic surface, we show that, as 𝛽 is decreased, the scaling of the effective slip length at small solid fractions is enhanced from the logarithmic scaling ln⁡(1/𝜀) for Newtonian fluids to the algebraic scaling 1/𝜀
1−𝑛
𝑛

, attained for 𝛽=𝒪⁡(𝜀
1−𝑛
𝑛

), 𝑛∈(0,1) being the exponent in the Carreau model. We illuminate this scaling enhancement and the geometric-rheological mechanism underlying it through asymptotic arguments and numerical simulations.