The origin and maintenance of mating preferences continues to be an important and controversial topic in sexual selection research. Leks and lek-like mating systems, where individuals gather in particular spots for the sole purpose of mate choice, are particularly puzzling, because the strong directional selection imposed by mate choice should erode genetic variation among competing individuals and negate any benefit for the choosing sex. Here, we take advantage of the lek-like mating system of the worm pipefish (Nerophis lumbriciformis) to test the phenotype-linked fertility hypothesis for the maintenance of mating preferences. We use microsatellite markers to perform a parentage analysis, along with a mark-recapture study, to confirm that the worm pipefish has an unusual mating system that strongly resembles a female lek, where females display and males visit the lek to choose mates. Our results show that the most highly ornamented females occupy positions near the centre of the breeding area, and males mating with these females receive fuller broods with larger eggs compared to males mating with less ornamented females. We also conduct a laboratory experiment to show that female ornaments are condition dependent and honestly signal reproductive potential. Overall, these results are consistent with the predictions of a sex-independent version of the phenotype-linked fertility hypothesis, as male preference for female ornaments correlates with fertility benefits.