Associative learning seems to be a general mechanism in animal cognition, reported in many phyla in its most elementary forms, and constitutes an excellent theoretical framework to understand how complex representations of the environment can be acquired, stored, and accessed. However, it is unclear how and when this cognitive ability would have appeared, and if it might have had a single origin, potentially specific to bilaterian animals. No updated view is available on the evolutionary importance and possible origin of this behavioral innovation, despite an old but rich literature on invertebrate learning, detailed knowledge of neurobiological mechanisms in some model species, and new insights on animal phylogeny. My aim is to provide such a statement, by integrating information from fields like comparative psychology, comparative neurobiology, phylogenetics, and evolutionary developmental biology; this would constitute the theoretical chapter of my PhD thesis. The rapid emergence of new animal models make it possible today to test evolutionary scenarios on behavior, consequently a global theoretical frame on associative learning in the animal kingdom could be of great value to help understanding the origin, thus the fundaments, of animal cognition.