The volume of major brain regions and the capacity for associative learning were compared between European (EHB) and African worker honey bees (AHB). Associative learning was measured in 14-day old workers and in foragers using proboscis extension response (PER) to odor-sugar water reward pairings. The brain volume of EHB and AHB workers was not significantly different, but mushroom body lobes were significantly larger in EHB. A higher proportion of AHB could not associate odor and reward compared with EHB. In EHB, 14 day old workers and foragers had similar PER rates. In AHB though, fewer foragers responded to initial odor-reward pairings than either 14 day old workers or EHB foragers. The results suggest that with foraging experience AHB require more odor-reward pairings before responding at levels comparable to nest bees or to EHB, and this might translate into a more conservative foraging strategy. Possible repercussions of the differences in PER between EHB and AHB foragers with respect to foraging efficiency are discussed.