The extent to which indirect genetic benefits can drive the evolution of directional mating preferences for more ornamented mates, and the mechanisms that maintain such preferences without depleting genetic variance, remain key questions in evolutionary ecology. We used an individual-based genetic model to examine whether a directional preference for mates with higher genome-wide heterozygosity (H), and consequently greater ornamentation, could evolve and be maintained in the absence of direct fitness benefits of mate choice. We specifically considered finite populations of varying size and spatial genetic structure, in which parent-offspring resemblance in heterozygosity could provide an indirect benefit of mate choice. A directional preference for heterozygous mates evolved under broad conditions, even given a substantial direct cost of mate choice, low mutation rate, and stochastic variation in the link between individual heterozygosity and ornamentation. Furthermore, genetic variance was retained under directional sexual selection. Preference evolution was strongest in smaller populations, but weaker in populations with greater internal genetic structure in which restricted dispersal increased local inbreeding among offspring of neighboring females that all preferentially mated with the same male. These results suggest that directional preferences for heterozygous or outbred mates could evolve and be maintained in finite populations in the absence of direct fitness benefits, suggesting a novel resolution to the lek paradox.