Bundeskanzler Willy Brandt leitete eine Neubestimmung der Politik der Bundesrepublik gegenüber den Staaten Osteuropas und der Sowjetunion ein. Parallel zu einem Wechsel von der heißen zur kalten Phase des Kalten Krieges im ganzen westlichen Bündnis wurden Konfrontationen abgebaut.
Brandts Berater Bahr hatte 1963 in einer Rede („Wandel durch Annäherung“) die Grundlagen für ein verändertes Verhältnis zur UdSSR, Polen und der DDR entworfen. Diese neue Ostpolitik setzte auf eine Wandlungsfähigkeit der Regime Osteuropas. Zentrale Voraussetzung für einen Wandel war die Anerkennung der Oder-Neiße-Grenze als Westgrenze Polens durch die Bundesrepublik. Die de facto-Anerkennung dieser Grenze vollzog die Bundesrepublik zunächst im Rahmen der Verhandlungen eines Vertrages mit Moskau (12.8.70).
Darin verpflichteten sich Bundesrepublik und UdSSR außerdem, auf Drohung und Anwendung von Gewalt zu verzichten und die territoriale Integrität aller Staaten in Europa zu achten. Die neue Politik war mit einem veränderten Verhältnis zur DDR verbunden. Beide Staaten verhandelten 1972 einen „Grundlagenvertrag“,
der eine gegenseitige Quasianerkennung festlegte. Ein eigene Staatsbürgerschaft der DDR akzeptierte die Bundesrepublik jedoch nicht. Sie behandelte weiterhin alle DDR-Flüchtlinge als Bundesbürger. Im Vertrag mit der Volksrepublik Polen (7.12.70), dessen Unterzeichnung durch den Kniefall Brandts vor dem Denkmal der Kämpfer des Warschauer Ghetto-Aufstandes Aufsehen erregte, wurde die bereits im Potsdamer Abkommen von 1945 vorgesehene (vorläufige) Westgrenze Polens von der Bundesrepublik akzeptiert, ein Verzicht auf alle Gebietsansprüche gegenüber Polen festgeschrieben und ein gegenseitiger Gewaltverzicht und der Austausch von Botschaftern vereinbart. In einer Anlage zum Vertrag erklärte die polnische Regierung sich bereit, Einwohner Polens mit unbestreitbar deutscher Volkszugehörigkeit ausreisen zu lassen. Sie wiederholte außerdem ihre Erklärung vom 24.8.53, auf weitere Reparationsleistungen zu verzichten. (Die Masse der polnischen Zwangsarbeiter erhielt erst nach der Jahrtausendwende eine minimale Erstattung ihres einbehaltenen Lohns.)
Die neue Ostpolitik stieß in der Bundesrepublik auf scharfe Kritik. Insbesondere die Unverletztlichkeitserklärung der polnischen Westgrenze wurde kritisiert. Fast wäre die Bundesregierung durch ein Mißtrauensvotum(25.4.1972) gestürzt worden. Die CDU/CSU–Opposition im Deutschen Bundestag sprach von einem „Ausverkauf deutscher Interessen“.
In der Volksrepublik Polen fand die Ostpolitik der Bundesrepublik hohe Aufmerksamkeit. Die Nachfahren Hitlers schienen sich zu wandeln. Die Ostpolitik der Bundesregierung ist jedoch auch von Oppositionellen im kommunistischen Polen kritisiert worden. Da sie auf eine Reformbereitschaft der Regime setzte und nicht auf die Freiheitsbewegungen in Osteuropa, habe sie
den Zusammenbruch dieser Regime verlangsamt. Zwar versuchten kommunistische Kommentatoren aus der DDR und aus Polen die neue Ostpolitik Willy Brandts mit der aggressiven Ostpolitik Hitlers und Bismarcks gleichzusetzen, dies hatte jedoch keine große Wirkung mehr. Willy Brandt hatte mit den "Kreuzrittern" nichts mehr gemein.