Parasitism in immature animals has been implicated in possible long-term consequences on the neurological performance and development of adult organisms. Here we investigated brain morphology and learning between worker honey bees, Apis mellifera, that were either parasitized or not parasitized during development by the ectoparasitic Varroa mite. Parasitism by Varroa decreased the honey bee host’s initial ability to learn odor cues associated with food reward. However, after several food-odor pairings, both groups responded equally well to odor cues. Honey bee learning was equally impaired in bees that were either infested with 1 mite or 2 mites. In addition, brain size and specific brain regions of the honey bee were reduced by approximately 13% in parasitized bees compared to non-parasitized sisters. In both groups, regions of the brain were conserved with an overall reduction in host size. Findings suggest that parasitism during development has lifelong consequences on the adult bee. Affected honey bees may have decreased abilities to forage, remember and communicate resources with nest mates.