The swimming behavior of a nematode Caenorhabditis elegans (C. elegans) is investigated in a non-Newtonian shear thinning colloidal suspension. At the onset value ([curly or open phi] [similar] 8%), the suspension begins to exhibit shear thinning behavior, and the average swimming speed of worms jumps by approximately 12% more than that measured in a Newtonian solution exhibiting no shear dependent viscosity. In the shear thinning regime, we observe a gradual yet significant improvement in swimming efficiency with an increase in [curly or open phi] while the swimming speed remains nearly constant. We postulate that this enhanced swimming can be explained by the temporal change in the stroke form of the nematode that is uniquely observed in a shear thinning colloidal suspension: the nematode features a fast and large stroke in its head to overcome the temporally high drag imposed by the viscous medium, whose effective viscosity ([small eta]s) is shown to drop drastically, inversely proportional to the strength of its stroke. Our results suggest new insights into how nematodes efficiently maneuver through the complex fluid environment in their natural habitat.