Во время службы в Германии он познакомился с австрийским дипломатом Клементом фон Меттернихом, который стал для Карла кумиром и образцом для подражания. Нессельроде всегда прислушивался к его советам, а тот использовал его поклонение в собственных целях. Поэтому со времени знакомства с Меттернихом главной целью Нессельроде стало тесное сближение с Австрией.

В 1807 году он был направлен в Тильзит под начало уполномоченных князей Лобанова и Куракина. Затем был назначен советником посольства в Париже. Поэтому все депеши Нессельроде писались от имени русского посла Толстого под влиянием Меттерниха. В них он крайне недоброжелательно отзывался о Франции, подготавливая почву для будущего союза России и Австрии.

В 1810 году Нессельроде по собственному желанию был отозван в Россию. Профранцузские настроения среди русского дворянства уже ослабели, и его ненависть к Франции пришлась ко двору. Александр I принял его ласково и назначил статс-секретарем, пожелав, чтобы в случае войны Нессельроде сопровождал его и отвечал за политическую переписку.

В 1812 году он женился на дочери министра финансов Гурьева, имевшего большое влияние при дворе, чем упрочил свое положение.

С 1812 по 1815 год Нессельроде находился при императоре и твердо отстаивал проавстрийские позиции. Однако канцлер Румянцев советовал Александру не доверять Австрии и спровоцировать в Австрии восстание славян, но император прислушался к мнению Нессельроде.

После победы над наполеоновскими войсками на территории России Кутузов советовал выйти из войны, но Нессельроде вместе с Румянцевым настояли на продолжении боевых действий на территории Германии, чтобы окончательно уничтожить французское могущество. И вновь Александр принял его сторону.

В 1815 году он присутствовал на Венском конгрессе, где обнаружилось наличие тайного договора между Францией и Австрией против России, что подорвало позиции Нессельроде. В 1816 году он стал управляющим Иностранной коллегией, однако император поручил ведение внешней политикой умному и самостоятельному графу Каподистрии, чьи взгляды в корне отличались от приоритетов Нессельроде.

В роли арбитра в противостоянии министров выступал Александр I, но его симпатии чаще склонялись в пользу Нессельроде. Именно его он брал с собой на конгрессы в Аахен, Троппау, Лайбах и Верону. В результате 1822 году граф Каподистрия был отстранен, и вся полнота власти перешла в руки Нессельроде, который продолжал придерживаться линии на сближение с Австрией.

Придя к власти в 1825 году, Николай I сохранил его влияние, и 1830 году в Карлсбаде Нессельроде снова встретился с Меттернихом, который отчитал его за оказание поддержки греческому восстанию, и послушный ученик признал справедливость этих упреков. В 1844 году Нессельроде занял пост канцлера.