Across sub-Saharan Africa, new democracies have emerged mainly in the context of relatively effective states. Using aggregate indicators of governance and new public opinion data, this article shows which aspects of state building are most important. The scope of state infrastructure and the delivery of welfare services have little impact. But the establishment of political order -especially as experienced through improvements in personal security- and the legitimacy of the state -as measured by leaders' adherence to a rule of law- are critical to democratization. But, because legitimacy is itself a product of democratization, studies of African states and regimes, presently separated, should be reconnected.