What explains contemporary variation in state capacity across African states? Recent research has focused on the possible role played by colonial and pre-colonial institutions. This paper investigates the way in which colonial and pre-colonial institutions interacted to affect the public legitimacy and coercive capacity of African states on independence. A coherent configuration of historical institutions, pre-colonial centralisation combined with colonial indirect rule through traditionally legitimate rulers, contrasts with the incoherent and comparatively illegitimate configurations of pre-colonial decentralisation with traditional rule and pre-colonial centralisation with colonial non-traditional or direct rule. The paper tests the theoretical expectations in a historical instrumental-variables framework.