This chapter examines for the first time in detail Greece’s reintegration into the military structure of NATO and the difficult negotiations that preceded it. With the influence of the Cold War in world affairs steadily diminishing, both Greece and Turkey openly prioritized their narrow national interests at the expense of the Alliance. Athens asked for a special relationship with NATO that would allow it to redirect its defence posture vis-à-vis Ankara while Ankara blocked Greek reintegration in order to strengthen its political and military position in the Aegean dispute, even though it was clear that Greek re-entry would be in the interest of all NATO members. The resurgence of the Cold War tipped the scales by increasing Ankara’s strategic importance to the West and simultaneously making it more vulnerable to external influence. Turkey was exposed to the new Cold War pressures and had to prove its commitment to the West by contributing to the stabilization of the southern flank of NATO. Instead of making concessions on the more sensitive issues of Cyprus and the Aegean, it chose to allow Greece’s re-entry, which remained high on the Western political agenda. In the long term, however, it seemed that Turkey’s increased strategic importance tended to undermine the balanced approach that the Greeks had forced the West to adopt.