Environmental variability and adaptive foraging behavior have been shown to favor coexistence of specialists and generalists on an ecological timescale. This leaves unaddressed the question of whether such coexistence can also be expected on an evolutionary timescale. In this article, we study the attainability, through gradual evolution, of specialist-generalist coexistence, as well as the evolutionary stability of such communities when allowing for immigration. Our analysis shows that the potential for specialist-generalist coexistence is much more restricted than originally thought and strongly depends on the trade-off structure assumed. We establish that ecological coexistence is less likely for species facing a trade-off between per capita reproduction in different habitats than when the trade-off acts on carrying capacities alone. We also demonstrate that coexistence is evolutionarily stable whenever it is ecologically stable but that in most cases, such coexistence cannot be reached through gradual evolution. We conclude that an evolutionarily stable community of specialists and generalists may be created only through immigration from elsewhere or through mutations of large effect. Our results highlight that trade-offs in fitness-determining traits can have counterintuitive effects on the evolution of specialization.