Abstract Spermatozoa vary enormously in their form and dimensions, both between and within species, yet how this variation translates into fertilizing efficiency is not known. Sperm swimming velocity is a key determinant of male fertilization success, but previous efforts to identity which sperm phenotypic traits are associated with swimming velocity have been unsuccessful. Here, we examine the relationship between the size of several sperm components and sperm swimming velocity in natural populations of red deer (Cervus elaphus hispanicus) where selective pressures to enhance male reproductive success are expected to be strong. Our results show that there is little within-male and considerable between-male variation in sperm dimensions. Spermatozoa with longer midpieces swim more slowly, a finding which does not support the hypothesis that the size of the midpiece determines the amount of energy which is translated into swimming speed. In contrast, spermatozoa with elongated heads, and those in which the relative length of the rest of the flagellum is longer, swim faster. Thus, the hydrodynamic shape of the head and the forces generated by the relative size of the rest of the flagellum seem to be the key determinants of sperm swimming velocity.