Для правительства ключи к новой «восточной политике» находились в Кремле. Без этих господ, через голову СССР ничего бы не сдвинулось в отношениях двух Германии и сосуществовании с восточноевропейскими соседями. Ситуация была более благоприятной, чем та, которую застала Большая коалиция. Москва серьезно конфликтовала с Пекином и искала покоя и разрядки на Западе. Чтобы сдвинуть с места отношения, нужен был подходящий человек. Вилли Брандт посчитал таковым статс-секретаря Эгона Бара. Тот был упорен и хитроумен, к тому же канцлер полностью ему доверял. Уже в 1963 году он сформулировал идею «перемен через сближение». Теперь это предстояло претворить в жизнь. В январе 1970 года Эгон Бар прилетел в Москву. Западные союзники не без опасения следили за новым курсом политического обновления. Белый дом не скрывал своего скепсиса относительно немецких действий в одиночку. Генеральный секретарь США, Генри Киссинджер, напомнил о том, что забыли посоветоваться с западным партнером. «Информация вместо консультации», — так звучал новый девиз Федеративной республики, которая таким образом подчеркивала свою независимости от США. «Я считаю себя канцлером не побежденной, а освобожденной Германии», самоуверенно заявил Вилли Брандт журналистам после выборов.
На протяжении примерно 50 заседаний с советским министром иностранных дел Громыко Эгон Бар смог заложить новый фундамент немецко-русских отношений. Когда после трехнедельного пребывания в Москве Бар вернулся наконец в Бонн, он привез с собой черновик текста договора с бывшим военным противником. Две недели спустя текст уже красовался на титульных страницах газеты «Бильд» под заголовком «Что было тайным до сих пор». Хотя соглашения, которые как-то просочились наружу, и были приведены не полностью, этого уже хватило, чтобы напугать западных немцев. Отказ ФРГ от будущих территориальных претензий и признание территориального статуса-кво в Европе, были в глазах общественности не чем иным, как «распродажей немецких интересов», ведь черным по белому было сказано, что Германия отказывается от территорий, потерянных во Второй мировой войне. Правительству с трудом удалось восстановить равновесие. В следующем раунде боев за договор участвовал Вальтер Шель. На даче Андрея Громыко оба министра иностранных дел пришли наконец к единому мнению, так родился Московский договор. Он содержал взаимные заверения в признании существующих европейских границ, в том числе и границы по линии Одер — Найсе, образующей «западную границу народной республики Польша, а также границу между ФРГ и ГДР».
11 августа канцлер прервал свой отпуск в Норвегии и вылетел и Москву. «Мы прилетели поздно, но мы прилетели», — многозначительно прокомментировал он опоздание своего самолета. На следующий день в Екатерининском зале Большого Кремлевского дворца состоялось праздничное подписание договора под бдительным оком главы государства и партии Леонида Ильича Брежнева. После церемонии Брежнев, с которым Брандт лично никогда раньше не встречался, отвел его в сторону и попросил о разговоре с глазу на глаз. Много часов спустя Брандт знал об опасениях советского лидера, который подарил канцлеру открытку с изображением Владимира Ленина и договорился о скорейшем подписании договора. Этот разговор послужил фундаментом для будущего согласия между обоими политиками. Вечером Брандт обратился с телеэкранов к своим соотечественникам. С подписанием этого договора не было потеряно ничего, что мы не проиграли бы уже давным-давно». Это было признание счетов, оставленных со времен Второй мировой войны. Брандт заявил, что готов их оплатить.