The state of the Congolese state has been subject to a heated debate, with some arguing that it remains mostly irrelevant outside its capital or even that there is no such thing as Congo. Others contend that there is no lack of state order in Congo, but that this order is characterised by predatory rule and (privatised) extortion. This paper wants to put both claims into perspective and to assess how different actors re-deploy various rationalities and practices of statehood. Based on fieldwork in South Kivu, this paper looks into the making of public authority in the territory of Kalehe (eastern DRC), where since the start of the Congo wars in 1996 a growing number of armed and other actors have claimed and exercised power. The paper stresses that these actors’ competing claims to public authority are intimately linked to struggles of territory and populations and tend to resemble and reproduce previous state practices and norms. The idea of the state seems to be one of the principal objects of reference deployed by these actors to legitimate their claims, mainly because it still resonates with the social imaginaries of public order.