Honeybees, Apis mellifera, readily learn to associate odours with sugar rewards and we show here that recall of the olfactory memory, as demonstrated by the bee extending its proboscis when presented with the trained odour, involves first the right and then the left antenna. At 1–2 hour after training using both antennae, recall is possible mainly when the bee uses its right antenna but by 6 hours after training a lateral shift has occurred and the memory can now be recalled mainly when the left antenna is in use. Long-term memory one day after training is also accessed mainly via the left antenna. This time-dependent shift from right to left antenna is also seen as side biases in responding to odour presented to the bee's left or right side. Hence, not only are the cellular events of memory formation similar in bees and vertebrate species but also the lateralized networks involved may be similar. These findings therefore seem to call for remarkable parallel evolution and suggest that the proper functioning of memory formation in a bilateral animal, either vertebrate or invertebrate, requires lateralization of processing.