Intelligence should evolve to help animals solve problems posed by the environment, but it remains unclear how complexity or novelty in the animal’s environment might facilitate evolutionary enhancement of cognition, or whether domain-general intelligence evolves in response to domain-specific selection pressures. The social complexity hypothesis, which posits that intelligence evolved to cope with the labile behavior of group-mates, has been strongly supported by work on the socio-cognitive abilities of primates and other animals. I review the remarkable convergence in social complexity between old-world primates and spotted hyenas, and describe our tests of the social complexity hypothesis in regard to both cognition and brain size in hyenas. Behavioral and morphological data indicate remarkable convergence between primates and hyenas with respect to their abilities in the domain of social cognition. However, social complexity fails to predict either brain volume or frontal cortex volume in a large array of mammalian carnivores. To inquire whether social complexity can explain the evolution of domain-general intelligence, we presented simple puzzles to members of 41 zoo-housed carnivore species, and found that species with larger relative brain size were better at solving the puzzles. However, social complexity failed to predict success in this task. Although social complexity appears to enhance social cognition, there are no clear causal links between social complexity and either brain size or performance in problem-solving tasks outside the social domain in mammalian carnivores, suggesting that foraging complexity, or complexity in other aspects of the physical environment, also likely affects the evolution of intelligence.