This paper 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 norms need to resonate with the dominant domestic discourse on political reforms. To substantiate our argument, we focus on the European Union’s (EU) anti-corruption 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 anti-corruption programs as an instrument against political opponents using enhanced state capacities to stabilize the incumbent regime. Only in Georgia, however, the fight against corruption was facilitated by sustained domestic mobilization for anti-corruption policies that added pressure on political elites ‘from below.’