In 1957 Polish foreign minister Adam Rapacki proposed the Rapacki Plan for a nuclear free zone in central Europe. Public opinion tended to be favourable in the West, but it was rejected by leaders of West Germany, Britain, France and the United States. They feared it would leave the powerful conventional armies of the Warsaw Pact dominant over the weaker NATO armies.

During November 1958, Khrushchev made an unsuccessful attempt to turn all of Berlin into an independent, demilitarized "free city". He gave the United States, Great Britain, and France a six-month ultimatum to withdraw their troops from the sectors they still occupied in West Berlin, or he would transfer control of Western access rights to the East Germans. Khrushchev earlier explained to Mao Zedong that "Berlin is the testicles of the West. Every time I want to make the West scream, I squeeze on Berlin." NATO formally rejected the ultimatum in mid-December and Khrushchev withdrew it in return for a Geneva conference on the German question.