This article, which forms the introduction to a collection of studies, focuses on processes of state construction and deconstruction in contemporary Africa. Its objective is to better understand how local, national and transnational actors forge and remake the state through processes of negotiation, contestation and bricolage. Following a critique of the predominant state failure literature and its normative and analytical shortcomings, the authors identify four key arguments of the scholarly literature on the state in Africa, which concern the historicity of the state in Africa, the embeddedness of bureaucratic organizations in society, the symbolic and material dimensions of statehood and the importance of legitimacy. A heuristic framework entitled ‘negotiating statehood' is proposed, referring to the dynamic and partly undetermined processes of state formation and failure by a multitude of social actors who compete over the institutionalization of power relations. The article then operationalizes this framework in three sections that partly conceptualize, partly illustrate who negotiates statehood in contemporary Africa (actors, resources and repertoires); where these negotiation processes occur (negotiation arenas and tables); and what these processes are all about (objects of negotiation). Empirical examples drawn from a variety of political contexts across the African continent illustrate these propositions.