Summary: The first bifurcation and the instability mechanisms of shear-thinning and shear-thickening fluids flowing past a circular cylinder are studied using linear theory and numerical simulations. Structural sensitivity analysis based on the idea of a ‘wavemaker’ is performed to identify the core of the instability. The shear-dependent viscosity is modelled by the Carreau model where the rheological parameters, i.e. the power-index and the material time constant, are chosen in the range \(0.4\leqslant n\leqslant 1.75\) and \(0.1\leqslant \lambda \leqslant 100\). We show how shear-thinning/shear-thickening effects destabilize/stabilize the flow dramatically when scaling the problem with the reference zero-shear-rate viscosity. These variations are explained by modifications of the steady base flow due to the shear-dependent viscosity; the instability mechanisms are only slightly changed. The characteristics of the base flow, drag coefficient and size of recirculation bubble are presented to assess shear-thinning effects. We demonstrate that at critical conditions the local Reynolds number in the core of the instability is around 50 as for Newtonian fluids. The perturbation kinetic energy budget is also considered to examine the physical mechanism of the instability.