Many microorganisms swim by rotating one or many helical flagella, often propelling themselves through fluids that exhibit both viscous and elastic qualities in response to deformations. In an effort to better understand the complex interaction between the fluid and body in such systems, we have studied numerically the force-free swimming of a rotating helix in a viscoelastic (Oldroyd-B) fluid. The introduction of viscoelasticity can either enhance or retard the swimming speed depending on the body geometry and the properties of the fluid (through a dimensionless Deborah number). The results are compared to recent experiments on a rotating helix immersed in a Boger fluid. Our findings bridge the gap between studies showing situationally dependent enhancement or retardation of swimming speed, and may help to clarify phenomena observed in a number of biological systems.