Given that minority ethno-political organizations are generally weaker than states yet seek to change their policies or remove the ruling regime from power, why would negotiation occur? States prefer to ignore or repress such organizations, which typically have little to offer in return amidst negotiations that can legitimize them while delegitimizing the state. When a challenging organization establishes governing structures and controls movement in part of a state’s territory, however, it can easily inflict significant economic and political costs on the state while also possessing a valuable asset to exchange for concessions. An organization with territorial control cannot be ignored, while the state will have a strong incentive to negotiate before the state loses more face, the group gains more legitimacy, neighboring states are more likely to invade, and the international community is more likely to formally recognize any facts on the ground as a new status quo. Our analysis of 118 organizations in the Middle East and North Africa from 1980–2004 reveals that territorial control is the most important determinant of intrastate negotiation. In regards to existing scholarship, this suggests that a certain type of successful violence works—not all violence and not only nonviolence—while certain types of strong organizations—those that control territory—are more likely to reach negotiations with the state than weak ones.