Complex coevolutionary feedbacks between female mating interval and male sperm traits have been hypothesized to explain the evolution and persistence of costly polyandry. Such feedbacks could potentially arise because polyandry creates sperm competition and consequent selection on male allocation to sperm traits, while the emerging sperm traits could create female sperm limitation and, hence, impose selection for increased polyandry. However, the hypothesis that costly polyandry could coevolve with male sperm dynamics has not been tested. We built a genetically explicit individual-based model to simulate simultaneous evolution of female mating interval and male allocation to sperm number versus longevity, where these two sperm traits trade off. We show that evolution of competing sperm traits under polyandry can indeed cause female sperm limitation and, hence, promote further evolution and persistence of costly polyandry, particularly when sperm are costly relative to the degree of female sperm limitation. These feedbacks were stronger, and greater polyandry evolved, when postcopulatory competition for paternity followed a loaded rather than fair raffle and when sperm traits had realistically low heritability. We therefore demonstrate that the evolution of allocation to sperm traits driven by sperm competition can prevent males from overcoming female sperm limitation, thereby driving ongoing evolution of costly polyandry.