For many years, Israel and the PLO adamantly refused to negotiate with one another. The former indicated that it would never “negotiate with terrorists,” presaging contemporary declarations by the US and others, whereas the latter refused to recognize the other party as even a legitimate political entity. Yet, despite many setbacks, Israeli and Palestinian leaders did eventually negotiate, secretly at first and then openly at the highest levels, leading to several agreements between them. The ultimate goals of each party have not changed substantially over time, but their willingness to pursue diplomatic mechanisms to achieve those goals has. What accounts for this shift in strategies? In this chapter, we explore the process by which initially reluctant protagonists come to accept diplomacy to resolve their conflicts; we refer to this as “softening up.” We do so by studying all pairs of rival states in the period 1946-1995.