Understanding the evolutionary mechanisms that maintain sex throughout nature despite its substantial direct costs is a longstanding challenge in biology. Previous work has shown that sexual recombination provides a key advantage in speeding adaptation, in part by separating beneficial mutations from deleterious hitchhikers. However, these earlier studies have focused on the effects of sex in a constant environment. Here, we show that recombination also provides a key advantage in fluctuating conditions, promoting the evolution of generalist phenotypes by reducing the pleiotropic costs of local adaptation. Using laboratory evolution in S. cerevisiae as a model system, we show that hitchhiking genetic load leads to pleiotropic costs and hence specialization in response to local adaptation in asexual but not in sexual lineages. This provides the first direct evidence that sex can be maintained over longer evolutionary timescales because it enables lineages to persist in the face of environmental change.