The evolution of female preference for male genetic quality remains a controversial topic in sexual selection research. One well-known problem, known as the lek paradox, lies in understanding how variation in genetic quality is maintained in spite of natural selection and sexual selection against low-quality alleles. Here, we theoretically investigate a scenario where females pay a direct fitness cost to avoid males carrying an autosomal segregation distorter. We show that preference evolution is greatly facilitated under such circumstances. Because the distorter is transmitted in a non-Mendelian fashion, it can be maintained in the population despite directional sexual selection. The preference helps females avoid fitness costs associated with the distorter. Interestingly, we find that preference evolution is limited if the choice allele induces a very strong preference or if distortion is very strong. Moreover, the preference can only persist in the presence of a signal that reliably indicates a male's distorter genotype. Hence, even in a system where the lek paradox does not play a major role, costly preferences can only spread under specific circumstances. We discuss the importance of distorter systems for the evolution of costly female choice and potential implications for the use of artificial distorters in pest control.