Cognition serves to resolve uncertainty. Living in social groups is widely seen as a source of uncertainty driving cognitive evolution, but sociality can also mitigate sources of uncertainty, reducing the need for cognition. Moreover, social systems are not simply external selection pressures, but rather arise from the decisions individuals make regarding who to interact with and how to behave. Thus, an understanding of how and why cognition evolves requires careful consideration of the co-evolutionary feedback loop between cognition and sociality. Here, we adopt ideas from information theory to evaluate how potential sources of uncertainty differ across species and social systems. Whereas cognitive research often focuses on identifying human-like abilities in other animals, we instead emphasise that animals need to make adaptive decisions to navigate socio-ecological trade-offs. These decisions can be viewed as feedback loops between perceiving and acting on information, which shape individuals’ immediate social interactions, and scale up to generate the structure of societies. Emerging group-level characteristics such as social structure, communication networks, and culture in turn produce the context in which decisions are made and so shape selection on the underlying cognitive processes. Thus, minds shape societies and societies shape minds.