Environmental variability and adaptive foraging behavior have been shown to favor coexistence of specialists and generalists on an ecological time scale. This leaves the question whether coexistence should also be expected on an evolutionary time scale. In this paper, we study gradual evolution towards the coexistence of specialists and generalists, as well as evolutionary stability of such communities when constructed through migration. Our analysis shows that the potential for coexistence of specialists and generalists is much more restricted than originally thought. The potential for coexistence is strongly dependent on the trade-off structure assumed. The ecological conditions for coexistence are much more restricted when the consumers face a trade-off between habitat-specific per capita reproduction than when the trade-off acts on carrying capacities. Moreover, coexistence is evolutionarily stable whenever it is ecologically stable, but cannot be reached through gradual evolution in most cases. We conclude that an evolutionarily stable community of specialists and generalists may only be created through immigration or mutations of large effect. Our results highlight that trade-offs in fitness-determining traits can have counterintuitive effects on the evolution of specialization.