It remains controversial whether the ability to represent the world from the perspective of another (mentalising), is confined to humans. To address this question, we combined computational models of mentalising with a new experimental setup of Guinea baboons living in a social colony, which required no direct human intervention or teaching. Baboons freely came to play a strategic coordination game via touchscreen devices with any other baboon (social condition), or alone (solo condition). In fact, in both conditions, they were interacting with an identical Artificial Agent. The ability to successfully coordinate with the Artificial Agent was better in the social than in the solo condition. A computational mentalising model that predicts the effect of one’s actions on the partners’ decisions accounted for baboon’s behaviour, much better than reinforcement learning, Bayesian or heuristic models that lacked mentalising components. Such computations accounted best for behaviour in the social condition only, because when they played alone, the same baboons used a win stay/lose switch strategy. Together, these findings indicate that computations required for mentalising are present in the Guinea baboon and provide an evolutionary advantageous for efficient coordination.