It is the differences between sperm and eggs that fundamentally underpin the differences between the sexes within reproduction. For males, it is theorized that widespread sperm competition leads to selection for investment in sperm numbers, achieved by minimizing sperm size within limited resources for spermatogenesis in the testis. Here, we empirically examine how sperm competition shapes sperm size, after more than 77 generations of experimental selection of replicate lines under either high or low sperm competition intensities in the promiscuous flour beetle Tribolium castaneum. After this experimental evolution, populations had diverged significantly in their sperm competitiveness, with sperm in ejaculates from males evolving under high sperm competition intensities gaining 20% greater paternity than sperm in ejaculates from males that had evolved under low sperm competition intensity. Males did not change their relative investment into sperm production following this experimental evolution, showing no difference in testis sizes between high and low intensity regimes. However, the more competitive males from high sperm competition intensity regimes had evolved significantly longer sperm and, across six independently selected lines, there was a significant association between the degree of divergence in sperm length and average sperm competitiveness. To determine whether such sperm elongation is costly, we used dietary restriction experiments, and revealed that protein-restricted males produced significantly shorter sperm. Our findings therefore demonstrate that sperm competition intensity can exert positive directional selection on sperm size, despite this being a costly reproductive trait.