This article asks under which conditions the state-building efforts of external actors in areas of limited statehood are likely to be effective. We argue that the legitimacy of the specific norms promoted by external actors among local actors is crucial for their success in strengthening state capacities. International efforts need to resonate with prevalent social norms. To substantiate this argument, we focus on the European Union's (EU) anticorruption programs and their implementation in one of the most corrupt regions in the world, the Southern Caucasus. We show that legitimacy can explain why the EU's fight against corruption helped reduce corruption in Georgia but not in Armenia. In both countries, political elites could selectively use anticorruption programs as an instrument against political opponents, using enhanced state capacities to stabilize the incumbent regime. Only in Georgia, however, was the fight against corruption facilitated by sustained domestic mobilization for anticorruption policies that added pressure on political elites “from below.”