Transitive inference is a form of deductive reasoning that has been suggested as one cognitive mechanism by which animals could learn the many relationships within their group's dominance hierarchy. This process thus bears relevance to the social intelligence hypothesis, which posits evolutionary links between various forms of social and nonsocial cognition. Recent evidence corroborates the link between social complexity and transitive inference and indicates that highly social animals may show superior transitive reasoning even in nonsocial contexts. We examined the relationship between social complexity and transitive inference in two species of prosimians, a group of primates that diverged from the common ancestor of monkeys, apes and humans over 50 million years ago. In experiment 1, highly social ringtailed lemurs, Lemur catta, outperformed the less social mongoose lemurs, Eulemur mongoz, in tests of transitive inference and showed more robust representations of the underlying ordinal relationships between the stimuli. In experiment 2, after training under a correction procedure that emphasized the underlying linear dimension of the series, both species showed similar transitive inference. This finding suggests that the two lemur species differ not in their fundamental ability to make transitive inferences, but rather in their predisposition to mentally organize information along a common underlying dimension. Together, these results support the hypothesis that social complexity is an important selective pressure for the evolution of cognitive abilities relevant to transitive reasoning.