We conduct experiments with flexible swimmers to address the impact of fluid viscoelasticity on their locomotion. The swimmers are composed of a magnetic head actuated in rotation by a frequency-controlled magnetic field and a flexible tail whose deformation leads to forward propulsion. We consider both viscous Newtonian and glucose-based Boger fluids with similar viscosities. We find that the elasticity of the fluid systematically enhances the locomotion speed of the swimmer, and that this enhancement increases with Deborah number. Using Particle Image Velocimetry to visualize the flow field, we find a significant difference in the amount of shear between the rear and leading parts of the swimmer head. We conjecture that viscoelastic normal stresses lead to a net elastic forces in the swimming direction and thus a faster swimming speed. ; Comment: 14 pages, 7 figures, 3 videos