To understand the evolution of a Theory of Mind, we need to understand the selective factors that might have jumpstarted its initial evolution. We argue that a subconscious, reflexive appreciation of others’ intentions, emotions, and perspectives is at the roots of even the most complex forms of Theory of Mind and that these abilities may have evolved because natural selection has favored individuals that are motivated to empathize with others and attend to their social interactions. These skills are adaptive because they are essential to forming strong, enduring social bonds, which in turn enhance reproductive success. We first review evidence from both humans and other animals indicating that reflexive and reflective mental state attributions are inextricably linked and play a crucial role in promoting affiliative social bonds. We next describe results from free-ranging female baboons showing that individuals who show high rates of affiliative behavior form stronger social bonds with other females. These bonds, in turn, are linked to fitness. We then provide data from three different types of social challenges (male immigration, changes in grooming behavior after the death of a close relative, and responses during playback experiments), suggesting that females who manifest high rates of affiliative behavior may also be more motivated to anticipate challenges, react adaptively to setbacks, and respond appropriately to social interactions