While virtually all polities enjoy uncontested international legal sovereignty, there are wide variations in statehood, that is, the monopoly over the means of violence and the ability of the state to make and implement policies. Areas of limited statehood are not, however, ungoverned spaces where anarchy and chaos prevail. The provision of collective goods and services is possible even under extremely adverse conditions of fragile or failed statehood. We specify the conditions under which external efforts at state-building and service provision by state and nonstate actors can achieve their goals. We focus on the extent to which external actors enhance the capacity (statehood) of authority structures in weak states, or directly contribute to the provision of collective goods and services, such as public health, clean environment, social security, and infrastructure. We argue that three factors determine success: legitimacy, task complexity, and institutionalization, including the provision of adequate resources.