На Парижском конгрессе, завершившем свою работу 18 (30) мац 1856 года, Россия подписала договор, зафиксировавший ее поражение Крымской войне. Самым тяжелым условием Парижского мира была статья о нейтрализации Черного моря, по которой России запрещалось иметь военный флот и строить прибрежные оборонительные сооружения.
После поражения в Крымской войне 15 апреля 1856 года Министерство иностранных дел возглавил Горчаков. Александр II, отдавая должное опыту, таланту, уму, остановил свой выбор именно на нем, несмотря на попытки Нессельроде помешать этому назначению.
Историк С.С. Татищев с назначением Горчакова связывал „крутой поворот во внешней политике России“. Новое направление внешней политики было обосновано министром в докладе Александру II и изложено в циркуляре от 21 августа 1856 года. В нем подчеркивалось желание российски правительства посвятить „преимущественную заботливость“ внутренним делам, распространяя свою деятельность за пределы империи, „лишь кои того безусловно потребуют положительные пользы России“. И, наконец знаменитая фраза: „Говорят, Россия сердится. Нет, Россия не сердится, а сосредоточивается“.
Сам Горчаков в отчете о работе министерства за 1856 год объяснял: так: „Россия мысленно сосредоточивалась не из чувства задетого самолюбия, а с осознанием силы и своих подлинных интересов. Однако она не отказывалась ни от попечения о своем достоинстве, ни от ранга, принадлежавшего ей среди великих держав Европы“. Более того, политика воздержания, которой решено было следовать, вовсе не исключала для российской дипломатии изучения возможностей и подготовки к заключению новых союзов, не принимая, однако, никаких обязательств в отношении кого-либо, пока собственные национальные интересы ей этого не предпишут».
Горчаков стремился проводить «национальную» политику, не жертвуя интересами России во имя чуждых ей политических целей, в том числе целей Священного союза. Он первым в своих депешах стал употреблять выражение: «государь и Россия». «До меня, — говорил Горчаков, — для Европы не существовало другого понятия по отношению к нашему Отечеству, как только „император“». Нессельроде укорял его за это. «Мы знаем только одного царя, говорил мой предместник: нам дела нет до России».
«Князь представляет собой одного из самых выдающихся государственных деятелей, — писал о Горчакове в дневнике в 1856 году сардинский поверенный в делах в Петербурге Филиппе Ольдоини, — это сугубо русский и либеральный министр, разумеется, в той мере, в какой это возможно в его стране… Человек он умный и приятный, но очень вспыльчив…»
Борьба за отмену ограничительных статей Парижского трактата стала стратегической целью внешнеполитического курса Горчакова на ближайшие полтора десятилетия. Для решения этой главной задачи нужны были союзники.
Александр II склонялся к сближению с Пруссией, но Горчаков признавал недостаточным союз со слабейшей из великих держав для возвращения России ее прежнего положения в Европе. Достижение положительного результата он связывал с тесным сотрудничеством с Францией. Александр II согласился с доводами дипломата. Горчаков предписывал российскому послу в Париже Киселеву передать Наполеону III, что Россия не будет мешать Франции завладеть Ниццей И Савойей.
Наполеон III, проводивший дипломатическую подготовку к войне с Австрией, также нуждался в скорейшем подписании русско-французского союза. В результате многочисленных встреч, споров и компромиссов 19 февраля (3 марта) 1859 года в Париже был подписан секретный русско-французский договор о нейтралитете и сотрудничестве. И хотя Россия не получила поддержки Франции при пересмотре статей Парижского мира, этот договор позволил ей выйти из изоляции, в которой она находилась после поражения в войне с Турцией.
В начале 1860-х годов Горчаков занимал видное положение в правительстве и оказывал большое влияние не только на внешнюю политику, но и на внутренние дела страны, выступая за проведение умеренных буржуазных реформ. Российскому министру был присвоен чин вице-канцлера (1862), а затем государственного канцлера (1867).