Some micro-organisms and artificial micro-swimmers propel at low Reynolds numbers (Re) via the interaction of their flexible appendages with the surrounding fluid. While their locomotion has been extensively studied with a Newtonian fluid assumption, in realistic biological environments these micro-swimmers invariably encounter rheologically complex fluids. In particular, many biological fluids such as blood and different types of mucus have shear-thinning viscosities. The influence of this ubiquitous non-Newtonian rheology on the performance of flexible swimmers remains largely unknown. Here, we present a first study to examine how shear-thinning rheology alters the fluid-structure interaction and hence the propulsion performance of elastic swimmers at low Re. Via a simple elastic swimmer actuated magnetically, we demonstrate that shear-thinning rheology can either enhance or hinder elastohydrodynamic propulsion, depending on the intricate interplay between elastic and viscous forces as well as the magnetic actuation. We also use a reduced-order model to elucidate the mechanisms underlying the enhanced and hindered propulsion observed in different physical regimes. These results and improved understanding could guide the design of flexible micro-swimmers in non-Newtonian fluids.