An extensive literature in political science shows how citizens' evaluations of politicians—as well as their electoral behavior—are affected by trait impressions of these politicians. However, deeper, interdisciplinary theory building that seeks to address when and for whom specific trait impressions come to guide candidate evaluations remains absent. In this article, I outline the theory of adaptive followership that seeks to address this shortcoming. Grounded in evolutionary psychology, I argue that leadership evolved as a solution to problems of intragroup coordination in ancestral small-scale societies. In order to understand the traits that drive followers' and voters' evaluations of leaders and politicians, one should therefore focus on problems related to group coordination and ask how these problems might regulate followers' prioritizations of various traits in leaders. On this basis, I outline an analytical framework consisting of three predictions that simultaneously formulate how (1) contexts and (2) individual differences of relevance to a given group-coordination problem regulate trait preferences, and (3) how such preferences differ between leaders and nonleaders (i.e., other social categories). The analytical framework is applied for structuring two reviews (including new empirical studies) of the ways through which intergroup conflict and disease threat, respectively, affect followers' trait preferences in leaders. Finally, directions and suggestions for future research on trait-based candidates and leader evaluations are discussed.