Хотя первоначально позиции сторон казались несовместимыми (СССР настаивал на международноправовом признании ГДР и недействительности Мюнхенского договора, ФРГ подчеркивала особый характер германо-германских отношений), им удалось найти компромисс в формуле, признающей нерушимость (а не неизменность) послевоенных границ. 12 августа 1970 г. Московский договор о сотрудничестве и отказе от применения силы подписан Брандтом и Н.А. Косыгиным. СССР и ФРГ заявляли о своей приверженности политике мира и разрядки, отсутствии территориальных претензий к любому из существующих государств и признании сложившихся в Европе реалий. Особое упоминание в тексте договора границы по Одеру и Нейсе, а также западных границ ГДР являлось несомненной победой советской дипломатии. Напротив, вопрос о Западном Берлине исключался из сферы его действия, поскольку по нему в то же самое время велись переговоры четырех державпобедительниц. В рамках протокола была согласована особая процедура, на которой настаивала западногерманская сторона. Параллельно с подписанием договора Шеель передал Громыко краткое «письмо о германском единстве», в котором подтверждалась приверженность мирному воссоединению Германии. Этот документ был без комментариев принят советской стороной и стал внутриполитической индульгенцией для правительства Брандта.
При всех своих недоговоренностях Московский договор являлся первым признанием ФРГ итогов второй мировой войны в Восточной Европе, открывая перспективу скорейшей нормализации отношений ФРГ с другими странами этого региона. 7 декабря 1970 аналогичный договор был подписан в Варшаве. В рамках дальнейших польско-западногерманских договоренностей была зафиксирована готовность к урегулированию взаимных претензий, оговорены условия выезда этнических немцев из Польши. Проблема компенсаций польским гражданам, пострадавшим в годы оккупации, была окончательно решена только в 1975 г. Западная Германия обязалась выплатить польскому правительству 1,3 млрд. марок и предоставить дополнительные кредиты на такую же сумму. Последний из серии договоров, ставивших на новую основу отношения ФРГ с восточными соседями, был подписан в Праге 11 декабря 1973.
Ратификация Московского и Варшавского договоров увязывалась правительством Брандта с решением вопроса о статусе Западного Берлина. Первоначальная позиция ФРГ, которую представляли на переговорах три западные державы, определялась принципом «все или ничего»: либо признать Западный Берлин частью ФРГ, либо распространить особый политической статус на весь Берлин. СССР на сей раз отказался от выдвижения ультиматумов, но настаивал на том, что западная часть города является «самостоятельным политическим образованием». Соглашение СССР, США, Великобритании и Франции, подписанное 3 сентября 1971 г., представляло собой сложную систему взаимных уступок, закрепившую сложившийся status quo. Особый правовой статус Западного Берлина обменивался на гарантии свободного транзита из ФРГ, последней разрешалось представлять интересы жителей этой части города за рубежом. Соглашение подразумевало запрет проведения государственных актов ФРГ (например, выборов президента) на территории Западного Берлина, хотя и не противодействовало их будничному «срастанию». СССР был вынуждены пойти на серьезные уступки в этом вопросе в обмен на обещание Запада признать ГДР, без чего здание «новой восточной политики» оставалось бы недостроенным.
С конца 1971 г. в ФРГ началась кампания ратификации договоров ФРГ с СССР и Польшей, надолго ставшая темой номер один в средствах массовой информации. Диапазон мнений расходился от «распродажи национальных интересов» до «необходимости поставить точку во второй мировой войне». ХДС/ХСС увидел в этой процедуре шанс политического реванша, для реализации которого использовались все доступные методы борьбы вплоть до блокады парламента союзами изгнанных и «утечки» секретных правительственных документов. Оппозиция, усилившая свои ряды несколькими перебежчиками из фракций СДПГ и СвДП, 27 апреля 1972 г. впервые попробовала объявить конструктивный вотум недоверия правительству. Для победы ей не хватило всего двух голосов. Голосование 27 апреля стало самым грязным в парламентской истории ФРГ, сопровождаясь взаимным переманиванием депутатов и покупкой их голосов, за каждый из которых выплачивалось около 50 тыс. марок. Тем не менее, как для социал-демократов, так и для принимавших участие в торге спецслужб ГДР цель оправдала затраченные средства – ратификация восточных договоров вновь обрела реальные очертания. Итогом парламентского компромисса стала резолюция всех фракций бундестага, в составлении которой тайно принимал участие и посол СССР в ФРГ В.М. Фалин. В ней подчеркивалось, что «договоренности не предвосхищают перспективы заключения мирного договора со всей Германией и не создают международно-правовой основы для существующих ныне границ». Ожидаемые протесты Москвы и Варшавы стали спасением лица для депутатов от ХДС/ХСС, воздержавшихся 17 мая 1972 г. при ратификации восточных договоров.