When it comes to the brain, bigger is generally considered better in terms of cognitive performance. While this notion is supported by studies of birds and primates showing that larger brains improve learning capacity, similar evidence is surprisingly lacking for invertebrates. Although the brain of invertebrates is smaller and simpler than that of vertebrates, recent work in insects has revealed enormous variation in size across species. Here, we ask whether bee species that have larger brains also have higher learning abilities. We conducted an experiment in which field-collected individuals had to associate an unconditioned stimulus (sucrose) with a conditioned stimulus (colored strip). We found that most species can learn to associate a color with a reward, yet some do so better than others. These differences in learning were related to brain size: species with larger brains — both absolute and relative to body size— exhibited enhanced performance to learn the reward-color association. Our finding highlights the functional significance of brain size in insects, filling a major gap in our understanding of brain evolution and opening new opportunities for future research.