A key objection raised by terrorism scholars and policymakers against engaging in negotiations with terrorists is that it legitimizes terrorist groups, their goals and their means. Talking to them would serve only to incite more violence and weaken the fabric of democratic states, they argue. With the emergence of Al-Qaeda and its complex transnational structure, many have added another objection: Who does one talk to? Faced with such a multifaceted, horizontal organization, how does one engage? This article offers an alternative approach to the question of legitimacy and complexity in engaging with terrorism. Drawing from research in peace and conflict studies, it analyses how these two factors may in fact be conducive to a nonviolent resolution of conflicts involving terrorist violence. Using the conflicts in Northern Ireland and the southern Philippine region of Mindanao as illustrations, the article argues that the legitimation of terrorist' groups through talks can be a means to transform a conflict away from violence, while complexity may in fact open up new possibilities for engagement. The article concludes by examining how the naming of a group as terrorist' can and is often designed to forestall nonviolent responses to terrorism.