In der Hauptstadt unterzeichnen er und seine polnischen Partner den Warschauer Vertrag. Die Oder-Neiße-Linie wird darin als Grenze festgeschrieben, und wie im Moskauer Vertrag bekennen sich die beiden Länder zur Gewaltfreiheit. Zuvor besucht Brandt zudem das Denkmal der Helden des Ghettos, das an den Warschauer Ghetto-Aufstand von 1943 erinnert. Vor dem Denkmal leistet Brandt Abbitte für die von Deutschen verübten Verbrechen: Das Bild des knienden Kanzlers geht um die Welt.

Brandt verleiht seiner Aussöhnungspolitik durch diese Geste eine größere Glaubwürdigkeit, als es jede verbale Beteuerung vermocht hätte. In seinen Erinnerungen schreibt er: "Am Abgrund der deutschen Geschichte und unter der Last der Millionen Ermordeten tat ich, was Menschen tun, wenn die Sprache versagt." Das amerikanische Time Magazine kürt Brandt 1970 zum Man of the Year. Im Jahr darauf, am 10. Dezember 1971, erhält er in Oslo den Friedensnobelpreis.

Eine Gratwanderung bleibt seine Entspannungspolitik trotz allem: Brandt weiß nur zu gut, dass die Bundesrepublik keinen Sonderweg einschlagen darf, der ins Niemandsland der Neutralität führt. "Unser nationales Interesse erlaubt es nicht, zwischen dem Westen und dem Osten zu stehen", erklärt er 1972. Nur auf der Basis der "Zusammenarbeit und Abstimmung mit dem Westen" soll "die Verständigung mit dem Osten" gesucht werden.

Dies betont Brandt nicht ohne Grund. Denn nicht nur in Ost-Berlin, Moskau und Warschau hat die Regierung Brandt mit ihrer Ostpolitik zunächst Misstrauen erregt, sondern auch im Westen. Die USA wollten den Partnern in Westdeutschland anfangs keine freie Hand beim Verhandeln mit den Sowjets lassen. Auch Frankreich äußerte seine Vorbehalte gegen Alleingänge der Bonner Regierung gen Osten. Brandt beteuerte immer wieder, die Bundesrepublik spreche mit Moskau "als zum Westen gehöriges Land". Die Bedenken in Paris und Washington konnte er aber nicht vollständig ausräumen.

Entsprechend schwierig verliefen die Viermächtegespräche über ein Berlin-Abkommen, die 1970 begannen: Die Siegermächte des Zweiten Weltkriegs hatten die deutsche Hauptstadt 1945 in vier Sektoren aufgeteilt. Nach Gründung der beiden deutschen Staaten 1949 behielt die Stadt ihren Sonderstatus; wie eine Insel lag der Westteil im DDR-Gebiet. Das Berlin-Abkommen, auf das sich Frankreich, Großbritannien, die Vereinigten Staaten und die Sowjetunion im September 1971 einigten, schrieb nun unter anderem einen "geregelten Zugang" von Westdeutschland aus durch die DDR zur Stadt fest.

Trotz solcher Erfolge ist Brandts Entspannungskurs in der Bundesrepublik auch in den frühen siebziger Jahren noch heftig umstritten. Die Blockadehaltung der Unionsparteien erschwert die Verhandlungen. Die Ratifizierung der vereinbarten Verträge durch den Bundestag scheint zeitweise unmöglich. Immer wieder werden Brandts Bemühungen von konservativer Seite als "Verzichtspolitik" diffamiert: Mit der Akzeptanz der Oder-Neiße-Grenze betreibe er den "Ausverkauf deutscher Interessen". 1970/71 gründet sich sogar eine gewaltbereite rechtsradikale Gruppe, die Aktion Widerstand, die Brandt Morddrohungen schickt. Gleichzeitig schrumpft die ohnehin nur knappe parlamentarische Mehrheit der rot-gelben Regierungskoalition, als prominente Nationalliberale aus der FDP und Flüchtlingsfunktionäre aus der SPD zur Opposition wechseln. Von April 1972 an besteht eine Pattsituation im Parlament.

Das Schicksal der Ostverträge und der Regierung Brandt scheint besiegelt zu sein, als die Opposition versucht, den Kanzler durch ein konstruktives Misstrauensvotum zu stürzen. Am 24. April 1972 stellt die CDU/CSU-Fraktion einen Antrag nach Artikel 67 des Grundgesetzes: "Der Bundestag spricht Bundeskanzler Willy Brandt das Misstrauen aus und wählt als seinen Nachfolger den Abgeordneten Dr. Rainer Barzel zum Bundeskanzler der Bundesrepublik Deutschland. Der Bundespräsident wird ersucht, den Bundeskanzler Willy Brandt zu entlassen."

Der Misstrauensantrag spaltet Deutschland in Befürworter und Gegner Brandts. Am 27. April stimmen die Parlamentarier ab. 249 Stimmen sind nötig, um Barzel zum Kanzler zu machen: Er erhält 247. Zwei Stimmen von CDU-Abgeordneten wurden gekauft – wie heute bekannt ist, von der Stasi –, um Brandt im Amt zu halten.

Nach diesem unerwarteten Scheitern des Kanzlersturzes endet der Konflikt in einer Niederlage für die Opposition. Die CDU-Spitze versucht ihre Fraktion nun zu überzeugen, den Verträgen von Moskau und Warschau zuzustimmen. Sie scheitert jedoch am Widerstand in den eigenen Reihen. Bei der Abstimmung über die Ostverträge am 17. Mai 1972 enthält sich die CDU/CSU-Fraktion zum überwiegenden Teil.

In einer Fernsehansprache weist Willy Brandt damals noch einmal ausdrücklich darauf hin, dass mit den Verträgen nichts verloren gehe, "was nicht längst verspielt worden" sei; noch einmal wirbt er für eine "Politik der Vernunft". Die Mehrheit der Wähler kann er damit überzeugen: Der klare Sieg der SPD bei der Bundestagswahl im November 1972 ist ein Ja zu Willy Brandt und seiner Politik der Entspannung. Mit dem Friedensnobelpreisträger identifizieren sich nun auch viele, die nicht zu den Anhängern der SPD zählen.

Großen Zuspruch erhält Brandt wenig später auch für den Grundlagenvertrag mit der DDR, den die Regierungen in Bonn und Ost-Berlin im Dezember 1972 unterschreiben. Die Vertragspartner vereinbaren, "gutnachbarliche Beziehungen" aufzubauen, die innerdeutschen Grenzen anzuerkennen, abzurüsten und auf Gewalt gegeneinander zu verzichten. In Umfragen stimmen vier Fünftel der Westdeutschen dem Vertrag zu. Die Unionsparteien hingegen laufen Sturm. Führende CDU- und CSU-Politiker bezeichnen den Vertrag als grundgesetzwidrig, weil er gegen das Wiedervereinigungsgebot verstoße. Die bayerische Staatsregierung ruft das Bundesverfassungsgericht an – doch ohne Erfolg: Die höchsten deutschen Richter bestätigen Brandts Politik.

Bürgern der Bundesrepublik, die Verwandte und Freunde im Ostteil des Landes haben, erleichtert der Grundlagenvertrag in vieler Hinsicht das Leben. Sie können nun leichter in den Osten reisen. Zudem wird es für Familien einfacher, die Kontakte über die Grenze hinweg zu halten. Die SED verbucht für sich, dass die Bundesregierung in Bonn künftig nicht mehr auf ihrem Alleinvertretungsanspruch beharrt und sich die DDR dadurch allmählich zu einem selbstständigen Akteur auf der internationalen Bühne entwickeln kann. So werden 1973 beide deutschen Staaten gemeinsam in die Vereinten Nationen aufgenommen.