Microorganisms are commonly found swimming in complex biological fluids such as mucus and these fluids respond elastically to deformation. These viscoelastic fluids have been previously shown to affect the swimming kinematics of these microorganisms in non-trivial ways depending on the rheology of the fluid, the particular swimming gait and the structural properties of the immersed body. In this report we put forth a previously unmentioned mechanism by which swimming organisms can experience a speed increase in a viscoelastic fluid. Using numerical simulations and asymptotic theory we find that significant swirling flow around a microscopic swimmer couples with the elasticity of the fluid to generate a marked increase in the swimming speed. We show that the speed enhancement is related to the introduction of mixed flow behind the swimmer and the presence of hoop stresses along its body. Furthermore, this effect persists when varying the fluid rheology and when considering different swimming gaits. This, combined with the generality of the phenomenon (i.e. the coupling of vortical flow with fluid elasticity near a microscopic swimmer), leads us to believe that this method of speed enhancement could be present for a wide range of microorganisms moving through complex fluids.