The presence of general intelligence poses a major evolutionary puzzle, which has led to increased interest in its presence in nonhuman animals. The aim of this review is to critically evaluate this puzzle, and to explore the implications for current theories about the evolution of cognition. We first review domain-general and domain-specific accounts of human cognition in order to situate attempts to identify general intelligence in nonhuman animals. Recent studies are consistent with the presence of general intelligence in mammals (rodents and primates). However, the interpretation of a psychometric g-factor as general intelligence needs to be validated, in particular in primates, and we propose a range of such tests. We then evaluate the implications of general intelligence in nonhuman animals for current theories about its evolution and find support for the cultural intelligence approach, which stresses the critical importance of social inputs during the ontogenetic construction of survival-relevant skills. The presence of general intelligence in nonhumans implies that modular abilities can arise in two ways, primarily through automatic development with fixed content and secondarily through learning and automatization with more variable content. The currently best-supported model, for humans and nonhuman vertebrates alike, thus construes the mind as a mix of skills based on primary and secondary modules. The relative importance of these two components is expected to vary widely among species, and we formulate tests to quantify their strength.