Phenotypic plasticity is the capacity for an individual genotype to produce different phenotypes in response to environmental variation. Most traits are plastic, but the degree to which plasticity is adaptive or non-adaptive depends on whether environmentally induced phenotypes are closer or further away from the local optimum. Existing theories make conflicting predictions about whether plasticity constrains or facilitates adaptive evolution. Debate persists because few empirical studies have tested the relationship between initial plasticity and subsequent adaptive evolution in natural populations. Here we show that the direction of plasticity in gene expression is generally opposite to the direction of adaptive evolution. We experimentally transplanted Trinidadian guppies (Poecilia reticulata) adapted to living with cichlid predators to cichlid-free streams, and tested for evolutionary divergence in brain gene expression patterns after three to four generations. We find 135 transcripts that evolved parallel changes in expression within the replicated introduction populations. These changes are in the same direction exhibited in a native cichlid-free population, suggesting rapid adaptive evolution. We find 89% of these transcripts exhibited non-adaptive plastic changes in expression when the source population was reared in the absence of predators, as they are in the opposite direction to the evolved changes. By contrast, the remaining transcripts exhibiting adaptive plasticity show reduced population divergence. Furthermore, the most plastic transcripts in the source population evolved reduced plasticity in the introduction populations, suggesting strong selection against non-adaptive plasticity. These results support models predicting that adaptive plasticity constrains evolution, whereas non-adaptive plasticity potentiates evolution by increasing the strength of directional selection. The role of non-adaptive plasticity in evolution has received relatively little attention; however, our results suggest that it may be an important mechanism that predicts evolutionary responses to new environments.