In Mozambique, the current legal framework institutionalizes a rural–urban differentiation of local governance, allowing for elected representation in thirty-three urban settings and the recognition of ‘community authorities’ in rural areas. This article deals with the latter by exploring the implementation of Decree 15/2000, which is the first legislation in post-colonial Mozambique to formalize ‘traditional authority’. Views of traditional authority as either a ‘genuine’ African form of authority legitimized by traditional beliefs and practices, or as a form of power ‘corrupted’ by colonial rule, are inadequate for understanding the current situation. In formerly war-torn Sussundenga District, kin-based authorities drew on elements from ‘traditional’ and ‘state-administrative’ domains of authority in order to be recognized. Varied definitions of tradition came to justify leadership, but the content on which legitimization was based defies any generalized Weberian dichotomy between traditional and modern/state types of office. Different sources of legitimacy sometimes foregrounded administrative needs and at other times maintained what became defined as traditional.