Statistical learning is a cognitive process for detecting regularities in sensory inputs typically presented as strings of sounds, shapes or objects, enabling species to predict future events thereby guiding decision-making and behavior. Such an adaptive trait has been demonstrated in vertebrates, including human and non-human primates, birds, and dogs. It remains unclear whether invertebrates, which possess smaller and simpler neural systems than vertebrates, can extract statistical information from sensory inputs. Here, we show for the first time that honey bees are able to learn and recall the temporal (statistical) structure of an olfactory stimulus. These results suggest that statistical learning is a fundamental component of a conserved cognitive toolkit present even in invertebrates.