The locomotion of microorganisms and spermatozoa in complex viscoelastic fluids is of critical importance in many biological processes such as fertilization, infection, and biofilm formation. Depending on their propulsion mechanisms, microswimmers display various responses to a complex fluid environment: increasing or decreasing their swimming speed and efficiency, modifying their propulsion kinematics and swimming gaits, and experiencing different hydrodynamic interactions with their surroundings. In this article, we review the fundamental physics of locomotion of biological and synthetic microswimmers in complex viscoelastic fluids. Starting from a continuum framework, we describe the main theoretical approaches developed to model microswimming in viscoelastic fluids, which typically rely on asymptotically small dimensionless parameters. We then summarise recent progress on the mobility of single cells propelled by cilia, waving flagella and rotating helical flagella in unbounded viscoelastic fluids. We next briefly discuss the impact of other physical factors, including the micro-scale heterogeneity of complex biological fluids, the role of Brownian fluctuations of the microswimmers, the effect of polymer entanglement and the influence of shear-thinning viscosity. In particular, for solutions of long polymer chains whose sizes are comparable to the radius of flagella, continuum models cannot be used and instead Brownian Dynamics for the polymers can predict the swimming dynamics. Finally, we discuss the effect of viscoelasticity on the dynamics of microswimmers in the presence of surfaces or external flows and its impact on collective cellular behavior.