The conventional wisdom holds that security in Iraq only improved after Gen. David Petraeus implemented a new counterinsurgency doctrine that stressed population security instead of aggressive operations against insurgent forces. This interpretation is strikingly similar to the historiography of the Huk Rebellion, the Malayan Emergency, and the Vietnam War. In each case observers criticized initial efforts as brutal and counterproductive, only to be rescued when enlightened new leaders arrived on the scene. This article challenges the familiar hero narrative, arguing that critics routinely exaggerate the importance of leadership changes because they view conflicts as experiments in counterinsurgency rather than exercises in state-building. Whereas counterinsurgency (COIN) theory emphasizes issues like public security and government legitimacy, theorists of state-building describe a bloody and protracted competition for power under conditions approaching anarchy. The upshot is that the “heroes” of late-stage COIN might actually depend on the earlier “villains” who did the dirty work of establishing political order and coercing the population into obedience.