Social life demands complex strategies for coordinating and competing with others. In humans, these strategies are supported by rich cognitive mechanisms, such as theory of mind. Theory of mind (i.e., mental state attribution, mentalizing, or mindreading) is the ability to track the unobservable mental states, like desires and beliefs, that guide others’ actions. Deeply social animals, like most nonhuman primates, would surely benefit from the adept capacity to interpret and predict others’ behavior that theory of mind affords. Yet, after forty years of investigation, the extent to which nonhuman primates represent the minds of others remains a topic of contentious debate. In the present chapter, we review evidence consistent with the possibility that monkeys and apes are capable of inferring others’ goals, perceptions, and beliefs. We then evaluate the quality of that evidence and point to the most prominent alternative explanations to be addressed by future research. Finally, we take a more broadly phylogenetic perspective, to identify evolutionary modifications to social cognition that have emerged throughout primate evolutionary history and to consider the selective pressures that may have driven those modifications. Taken together, this approach sheds light on the complex mechanisms that define the social minds of humans and other primates.