Sexual imprinting is the learning of a mate preference by direct observation of the phenotype of another member of the population. Sexual imprinting can be paternal, maternal, or oblique if individuals learn to prefer the phenotypes of their fathers, mothers, or other members of the population, respectively. Which phenotypes are learned can affect trait evolution and speciation rates. “Good genes” models of polygynous systems predict that females should evolve to imprint on their fathers, because paternal imprinting helps females to choose mates that will produce offspring that are both viable and sexy. Sexual imprinting by males has been observed in nature, but a theory for the evolution of sexual imprinting by males does not exist. We developed a good genes model to study the conditions under which sexual imprinting by males or by both sexes can evolve and to ask which sexual imprinting strategies maximize the fitness of the choosy sex. We found that when only males imprint, maternal imprinting is the most advantageous strategy. When both sexes imprint, it is most advantageous for both sexes to use paternal imprinting. Previous theory suggests that, in a given population, either males or females but not both will evolve choosiness in mating. We show how environmental change can lead to the evolution of sexual imprinting behavior by both sexes in the same population.