Angesichts der veränderten Situation, die sich durch die Einbindung der Bundesrepublik in die westlichen Bündnisse ergab, lud die sowjetische Führung Bundeskanzler Konrad Adenauer am 7. Juni 1955 mit einer diplomatischen Note zu Gesprächen über die Aufnahme diplomatischer Beziehungen nach Moskau ein. Nach Konsultationen mit den Westalliierten nahm Adenauer diese Einladung zwischen dem 8. und dem 14. September wahr. In nervenaufreibenden Gesprächen und Verhandlungen, bei denen die sowjetischen Unterhändler zwischen jovial-verbindlichem und offensiv-anklagendem Ton abrupt wechselten, wurde schließlich eine Einigung erzielt: Vereinbart wurde die Aufnahme diplomatischer Beziehungen, und die Sowjets gaben als Gegenleistung die mündliche Zusage, alle noch in der Sowjetunion befindlichen deutschen Kriegsgefangenen und Zivilinternierten freizulassen. Brieflich stellte Adenauer ausdrücklich den westdeutschen Vorbehalt bezüglich der Anerkennung der Ostgrenze fest und bekräftigte den Alleinvertretungsanspruch der Bundesrepublik für alle Deutschen. Um außerdem eine internationale Anerkennung der DDR durch weitere Staaten zu verhindern, wurde die im wesentlichen von Wilhelm Grewe, dem Leiter der Politischen Abteilung im Auswärtigen Amt entwickelte und nach Walter Hallstein, dem Staatssekretär im Auswärtigen Amt, benannte Hallstein-Doktrin verabschiedet. Sie drohte Staaten im Fall der Anerkennung der DDR mit dem Abbruch der diplomatischen Beziehungen durch die Bundesrepublik. Im Bild sind die Delegationen am 11. September 1955 vor der ehemaligen Datscha Maxim Gorkis zu sehen, welche die sowjetischen Gastgeber der deutschen Delegation zur Verfügung gestellt hatten (v.l. n.r.): Nikolaj Bulganin (Vorsitzender des Ministerrrates), Konrad Adenauer, Nikita Chruschtschow (Erster Sekretär des Zentralkomitees der KPdSU), Michail Perwuchin (Erster Stellvertreter des Vorsitzenden des Ministerrates); links hinter Adenauer steht Kurt-Georg Kiesinger (damals Vorsitzender des Auswärtigen Ausschusses des Bundestages).