Genome duplication (generating polyploids) is an engine of novelty in eukaryotic evolution and a promising crop improvement tool. Yet newly formed polyploids often have low fertility. Here we report that a severe fertility-compromising defect in pollen tube tip growth arises in new polyploids of Arabidopsis arenosa. Pollen tubes of newly polyploid A. arenosa grow slowly, have aberrant anatomy and disrupted physiology, often burst prematurely, and have altered gene expression. These phenotypes recover in evolved polyploids. We also show that gametophytic (pollen tube) genotypes of two tip-growth genes under selection in natural tetraploid A. arenosa are strongly associated with pollen tube performance in the tetraploid. Our work establishes pollen tube tip growth as an important fertility challenge for neo-polyploid plants and provides insights into a naturally evolved multigenic solution.