Despite the widespread assumption that the learning abilities of animals are adapted to the particular environments in which they operate, the quantitative effects of learning performance on fitness remain virtually unknown. Here, we evaluate the learning performance of bumble-bees (Bombus terrestris) from multiple colonies in an ecologically relevant associative learning task under laboratory conditions, before testing the foraging performance of the same colonies under the field conditions. We demonstrate that variation in learning speed among bumble-bee colonies is directly correlated with the foraging performance, a robust fitness measure, under natural conditions. Colonies vary in learning speed by a factor of nearly five, with the slowest learning colonies collecting 40% less nectar than the fastest learning colonies. Such a steep fitness function is suggestive of strong selection for higher learning speed. Partial correlation analysis reveals that other factors such as forager body size or colour preference appear to be negligible in our study. Although our study does not directly prove causality of learning on foraging success, our approach of correlating natural within-species variation in these two factors represents a major advance over traditional between-species correlative analyses where comparability can be compromised by the fact that species vary along multiple dimensions.