As the primary source of colony reproduction, social insect queens play a vital role. However, the cognitive abilities of queens are not well understood, although queen learning and memory are essential in multiple species such as honey bees, in which virgin queens must leave the nest and then successful learn to navigate back over repeated nuptial flights. Because honey bee queen learning has never been previously demonstrated, and our goal was to determine formally if Apis mellifera queens have learning and memory. We tested olfactory learning in queens and workers and examined the role of DNA methylation, which plays a key role in long term memory formation. We provide the first evidence that honey bee queens have remarkably good learning and memory. The proportion of honey bee queens that exhibited learning was 5-fold higher than workers at every tested age and, for memory, 4-fold higher than workers at a very young age. DNA methylation evidently plays a key role in superior queen memory because queens exhibiting remote memory had a more consistent elevation in Dnmt3 gene expression as compared to workers. Both castes also showed excellent very long-term memory (remote memory, 7 d), which was reduced by 30-36% by the DNA methylation inhibitor, Dnmt3. Given that queens live about 10-fold longer than workers, these results suggest that queens can serve as an exceptionally long-term reservoir of colony memory.