Technical Abstract: Phenotypic plasticity represents one of the most important ways that organisms adaptively respond to environmental variation. Alternate phenotypes produced through phenotypic plasiticity generally arise through conditional gene expression, which is predicted to result in relaxed selective constraint. However, ancestral relaxation of selection on genes may also act as a predecessor to the evolution of conditional gene expression. Thus, whether relaxed selection acts primarily as a cause or consequence of conditional gene expression remains unclear. Here we show that genes with diminished selective constraints have a higher propensity for evolving conditional expression associated with phenotypic plasticity. By analyzing gene expression patterns associated with specialized castes, sexes, and developmental stages in the fire ant Solenopsis invicta, we first show that the rate of molecular evolution is higher for conditionally expressed genes than those with ubiquitous expression. Surprisingly, we also find that orthologs of genes with caste-biased expression in either S. invicta or the honeybee Apis mellifera exhibit elevated lineage-specific rates of amino acid substitution in taxa lacking castes. Our results indicate that relaxed selection precedes differential gene expression and plays an underappreciated role in the evolution of phenotypic plasticity.