A major goal of modern evolutionary biology is to understand the causes and consequences of phenotypic plasticity, the ability of a single genotype to produce multiple phenotypes in response to variable environments. While ecological and quantitative genetic studies have evaluated models of the evolution of adaptive plasticity, some long-standing questions about plasticity require more mechanistic approaches. Here, we address two of those questions: does plasticity facilitate adaptive evolution? And do physiological costs place limits on plasticity? We examine these questions by comparing genetically and plastically regulated behavioural variation in sailfin mollies (Poecilia latipinna), which exhibit striking variation in plasticity for male mating behaviour. In this species, some genotypes respond plastically to a change in the social environment by switching between primarily courting and primarily sneaking behaviour. In contrast, other genotypes have fixed mating strategies (either courting or sneaking) and do not display plasticity. We found that genetic and plastic variation in behaviour were accompanied by partially, but not completely overlapping changes in brain gene expression, in partial support of models that predict that plasticity can facilitate adaptive evolution. We also found that behavioural plasticity was accompanied by broader and more robust changes in brain gene expression, suggesting a substantial physiological cost to plasticity. We also observed that sneaking behaviour, but not courting, was associated with upregulation of genes involved in learning and memory, suggesting that sneaking is more cognitively demanding than courtship.