Many important biological functions depend on microorganisms' ability to move in viscoelastic fluids such as mucus and wet soil. The effects of fluid elasticity on motility remain poorly understood partly because the swimmer strokes depend on the properties of the fluid medium, which obfuscates the mechanisms responsible for observed behavioural changes. We use experimental data on the gaits of Chlamydomonas reinhardtii swimming in Newtonian and viscoelastic fluids as inputs to numerical simulations that decouple the swimmer gait and fluid type in order to isolate the effect of fluid elasticity on swimming. In viscoelastic fluids, cells employing the Newtonian gait swim faster but generate larger stresses and use more power, and as a result the viscoelastic gait is more efficient. Furthermore, we show that fundamental principles of swimming based on viscous fluid theory miss important flow dynamics: fluid elasticity provides an elastic memory effect which increases both the forward and backward speeds, and (unlike purely viscous fluids) larger fluid stress accumulates around flagella moving tangent to the swimming direction, compared to the normal direction.