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