Variation in protein sequence and gene expression each contribute to phenotypic diversity, and may be subject to similar selective pressures. Eusocial insects are particularly useful for investigating the evolutionary link between protein sequence and condition-dependent patterns of gene expression because gene expression plays a central role in determining differences between eusocial insect sexes and castes. We investigated the relationship between protein coding sequence evolution and gene expression patterns in the fire ants Solenopsis invicta, S. richteri, and their hybrids to gain greater insight into how selection jointly operates on gene expression and coding sequence. We found that genes with high expression variability within castes and sexes were frequently differentially expressed between castes and sexes, as well as between species and hybrids. These results indicate that genes showing high variation in expression in one context also tend to show high variation in expression in other contexts. Our analyses further revealed that variation in both intra- and interspecific gene expression was positively associated with rate of protein sequence evolution in Solenopsis. This suggests that selective constraints on a gene operate both at the level of protein sequence and at the level of gene expression regulation. Overall, our study provides one of the strongest demonstrations that selective constraints mediate both protein sequence evolution and gene expression variability across different biological contexts and timescales.