Swimming micro-organisms often have to propel themselves in complex non-Newtonian fluids. We carry out experiments with self-propelling helical swimmers driven by an externally rotating magnetic field in shear-thinning inelastic fluids. Similarly to swimming in a Newtonian fluid, we obtain for each fluid a locomotion speed that scales linearly with the rotation frequency of the swimmer, but with a prefactor that depends on the power index of the fluid. The fluid is seen to always increase the swimming speed of the helix, up to 50 % faster, and thus the strongest of such type reported to date. The maximum relative increase is for a fluid power index of approximately 0.6. Using simple scalings, we argue that the speed increase is not due directly to the local decrease of the flow viscosity around the helical filament, but hypothesise instead that it originates from confinement-like effect due to viscosity stratification around the swimmer.