Natural selection optimizes an organism's genotype within the context of its environment. Adaptations to one environment can decrease fitness in another, revealing evolutionary trade-offs. Here, we show that the cost of gene expression underlies a trade-off between growth rate and mating efficiency in the yeast Saccharomyces cerevisiae. During asexual growth, mutations that eliminate the ability to mate provide an approximately 2% per-generation growth-rate advantage. Some strains, including most laboratory strains, carry an allele of GPA1 (an upstream component of the mating pathway) that increases mating efficiency by approximately 30% per round of mating at the cost of an approximately 1% per-generation growth-rate disadvantage. In addition to demonstrating a trade-off between growth rate and mating efficiency, our results illustrate differences in the selective pressures defining fitness in the laboratory versus the natural environment and show that selection, acting on the cost of gene expression, can optimize expression levels and promote gene loss.