The fact that individuals learn can change the relationship between genotype and phenotype in the population, and thus affect the evolutionary response to selection. Here we ask how male ability to learn from female response affects the evolution of a novel male behavioral courtship trait under pre-existing female preference (sensory drive). We assume a courtship trait which has both a genetic and a learned component, and a two-level female response to males. With individual-based simulations we show that, under this scenario, learning generally increases the strength of selection on the genetic component of the courtship trait, at least when the population genetic mean is still low. As a consequence, learning not only accelerates the evolution of the courtship trait, but also enables it when the trait is costly, which in the absence of learning results in an adaptive valley. Furthermore, learning can enable the evolution of the novel trait in the face of gene flow mediated by immigration of males that show superior attractiveness to females based on another, non-heritable trait. However, rather than increasing monotonically with the speed of learning, the effect of learning on evolution is maximized at intermediate learning rates. This model shows that, at least under some scenarios, the ability to learn can drive the evolution of mating behaviors through a process equivalent to Waddington's genetic assimilation.