State legitimacy – particularly its alleged potential to counter state fragility – has received increasing attention in academic and policy literature concerned with African development. Service provision can substantially influence such state legitimacy. Services, however, are mostly provided by a multiplicity of (state and non-state) providers. This article therefore specifically explores how joint service delivery by multiple providers shapes the attribution of state legitimacy in Burundi by means of two qualitative case studies. Empirically, the article demonstrates, first, that the process of stakeholder interaction, rather than the output of this process, most distinctly shapes state legitimacy and, second, that there are substantial variations in legitimacy attribution by different stakeholders and for different state institutions. Epistemologically, the article suggests three specific challenges that merit attention in further empirical investigation of state legitimacy in fragile settings: the diversity of people’s expectations; the artificiality of state/non-state distinctions; and the personification and politicization of state institutions.