In order to improve our understanding of the self-propulsion of swimming microorganisms in viscoelastic fluids, we study experimentally the locomotion of three artificial macro-scale swimmers in Newtonian and synthetic Boger fluids. Each swimmer is made of a rigid head and a tail whose dynamics leads to viscous propulsion. By considering three different kinematics of the tail (helical rigid, planar flexible, and helical flexible) in the same fluid, we demonstrate experimentally that the impact of viscoelasticity on the locomotion speed of the swimmers depends crucially on the kinematics of the tails. Specifically, rigid helical swimmers see no change in their swimming speed, swimmers with planar rod-like flexible tails always swim faster, while those with flexible ribbon-like tails undergoing helical deformation go systematically slower. Our study points to a subtle interplay between tail deformation, actuation, and viscoelastic stresses, and is relevant to the three-dimensional dynamics of flagellated cells in non-Newtonian fluids.