Вскоре после вступления на пост министра иностранных дел Горчаков сказал одному из своих близких сотрудников, что «ищет человека, который помог бы ему уничтожить параграфы Парижского тракта, касающиеся черноморского флота и границы Бессарабии; что он его ищет и найдёт». Добиться отмены статей трактата Россия могла только при поддержке сильных союзников. События Крымской войны показали, что их нельзя найти в немецких государствах, на которые ориентировалась дипломатия Нессельроде. Среди русского либерально-дворянского общества получила широкое распространение идея союза с Францией. Выразителем этих настроений стал Горчаков, который был убеждённым сторонником русско-французского сближения. Он называл союз России и Франции «естественным», что было весьма дальновидно.
При этом Горчаков исходил из реальных оснований. Франция стремилась к территориальным захватам в Европе, причём ближайшим объектом должны были стать итальянские владения Австрии. Воинственные намерения французского кабинета вызвали враждебное отношение Англии. Раскол среди недавних противников России, наметившийся уже во время Парижского конгресса, стал очевидностью. В этих условиях Франция была заинтересована в русской поддержке. Горчаков рассчитывал использовать эту заинтересованность с целью добиться отмены нейтрализации Чёрного моря — этого недавнего позора России.
Политика есть политика, поэтому обмен любезностями между недавними противниками начался сразу же после войны. Послом в Париже был назначен, как говорилось, один из видных
государственных деятелей России граф Киселёв. Наполеон III назначил французским представителем в Петербург своего любимца графа Морни. В русской столице Морни приняли с подчёркнутым вниманием. Вскоре взаимный зондаж о сближении Франции и России был продолжен на самом высоком уровне.
13 сентября 1857 года в Штутгарте состоялось свидание Александра II и Горчакова с Наполеоном III и его министром иностранных дел графом Валевским. Переговоры велись в общей форме, но когда Наполеон намекнул на возможность франко-австрийской войны и спросил, какова будет здесь точка зрения России, царь ответил, что он «не повторит ошибки 1849 года», то есть не окажет никакой помощи Австрии. Взамен французский император обещал Александру II поддержку в «восточном вопросе». Горчаков и Валевский вслед затем договорились, что посланникам обоих государств в Турции будет дано указание действовать совместно. Для нас это был уже кое-какой успех!
Правда, уже в этих переговорах наметились опасные разногласия между договаривающимися сторонами. Подготовленный Горчаковым проект русско-французского союза не был подписан императорами. Наполеон III затронул польский вопрос, прозрачно намекнув, что французское правительство поддерживает идею независимости Польши. Это вызвало сильное раздражение царя. «Со мной осмелились заговорить о Польше», — сказал он своим приближённым. Оба главы государства не были всё же крупными политическими деятелями... Но об этом позже.
Тем Не менее из наметившегося сближения с Францией русской дипломатии вскоре же удалось извлечь непосредственную выгоду. Летом 1858 года в Париже была созвана международная конференция для определения государственного устройства Дунайских княжеств. Россия стояла за их объединение. В Петербурге рассчитывали получить в новом государстве опору для упрочения своего влияния на Балканах. Благодаря поддержке Франции русскому представителю на конференции Киселёву удалось преодолеть сопротивление Англии и Австрии и добиться признания «Соединённых княжеств Молдавии и Валахии» в качестве отдельной державы.
Тут необходимы пояснения: вскоре после Парижской конференции произошло фактическое слияние обоих княжеств в одно государство — Румынию. Турция, поддержанная Австрией и Англией, начала готовиться к наступлению против молодого государства. Чтобы предупредить интервенцию, Горчаков заявил о намерении правительства России выступить в защиту Румынии. Он писал Киселёву в начале 1859 года, что никакая интервенция в Румынию недопустима. В Вене и Константинополе вынуждены были отступить. В 1858—1859 годах французская дипломатия оказала также содействие выступлению России в защиту Черногории и Сербии от посягательств Турции и Австрии. Это очень повысило традиционный авторитет России среди западных славян и в православной Греции.
В начале декабря 1858 года в Петербург прибыл с совершенно секретной миссией личный представитель французского императора Ле Нури для заключения франко-русского союза. Переговоры с ним вёл Горчаков. Позже министр иностранных дел представил Александру II доклад, в котором дал тонкий анализ подлинных целей французской политики. Наполеон предлагал России выступить против Австрии, обещая взамен Галицию и неопределённую гарантию содействовать отмене Парижского трактата.