К сожалению, ее щедрость спровоцировал отказ, сопровождавшийся личным оскорблением. Д’Аламбер не только вновь не согласился приехать в Россию, но также высказал замечание, которое имело публичную огласку. Ссылаясь на официальную, изложенную Екатериной версию смерти Петра III, он сказал: «Я имею большую склонность к геморрою, приводящему здесь, в России, к столь тяжким последствиям. Поэтому я предпочитаю, чтобы мой больной зад оставался в безопасности у меня дома». Императрица никогда не простила его.
Летом 1771 года Павел, которому исполнилось уже семнадцать лет, в течение пяти недель сражался с тяжелым гриппом. Екатерина и Панин с тревогой наблюдали за тем, как он переносит сильный жар и изнуряющую диарею. Когда же Павел поправился, вновь встал вопрос о наследовании. Екатерина знала, что не может откладывать его решение надолго, им нужно было заняться сразу же после наступления восемнадцатилетия Павла в сентябре 1772 года. Именно от Панина исходило предложение о том, что брак со здоровой молодой женщиной поможет этому слабому здоровьем юноше возмужать. Наставник также добавил, что, возможно, Ее Величество в этом случае получит внука, которого сможет воспитать в соответствии со своими взглядами. Этот довод убедил Екатерину.
Тремя годами ранее, в 1768-м, когда Павлу было четырнадцать, Екатерина уже стала задумываться о подходящей для него невесте и составила список претенденток. Характерно, что она подбирала невесту по своему подобию: разумную немецкую принцессу из небольшого княжества. Одной из девушек, привлекших ее внимание, оказалась София Вюртембергская, но Софии ко времени восемнадцатилетия Павла исполнилось только четырнадцать, и она была слишком юной для брака. Императрица переключила внимание на младших дочерей ландграфа Гессен-Дармштадтского. В планы Екатерины входило пригласить в Россию ландграфиню с тремя ее незамужними дочерьми: Амалией, Вильгельминой и Луизой. Им было восемнадцать, семнадцать и пятнадцать, соответственно. Павлу предстояло выбрать одну из них. Как и в случае с самой Екатериной много лет назад, отца девушек приглашать не стали.
Летом 1772 года после того, как Григория Орлова отправили в отставку, отношения Екатерины и ее сына стали налаживаться. Екатерина жила вместе с Павлом в Царском Селе и стала компаньонкой своего сына. Казалось, что отчужденность между ними была преодолена. «В моей жизни не было более радостного времени, чем те девять недель в Царском Селе, которые я провела с моим сыном, ставшим моим милым другом. Кажется, ему действительно доставляло удовольствие мое общество, – писала она своей гамбургской подруге фрау Бильке. – Я вернусь в город во вторник вместе с моим сыном, который не хочет покидать меня и которому я имела честь доставить столько радости, что иногда он даже вскакивал со своего места за столом и садился подле меня». Затем, после того как Павел решил, что Орлов исчез навсегда, Григорий снова появился при дворе. Павел пришел в уныние.
Весной 1773 года три гессенские принцессы и их мать были приглашены в Россию. Сначала они остановились в Берлине, как и в случае с Софией Ангальт-Цербстской тридцать один год назад, Фридрих напомнил, что они не должны забывать о своем немецком происхождении. К концу июня четыре русских корабля прибыли в Любек и повезли немецких гостей по Балтике. Фрегатом, на котором находились три молодые женщины и их мать, командовал лучший друг Павла, Андрей Разумовский, сын друга Екатерины – Кирилла Разумовского. Андрей был очарован средней дочерью, Вильгельминой, она также ответила ему взаимностью.
В Санкт-Петербурге Павлу понадобилось только два дня, чтобы сделать свой выбор, и он совпал с выбором Андрея Разумовского – это была принцесса Вильгельмина. К сожалению, реакция девушки на невысокого, странного молодого человека, предназначенного ей в мужья, была лишена энтузиазма. Екатерина обратила внимание на ее колебания, заметила это и ее мать. Тем не менее дальнейшие события развивались в соответствии с требованиями дипломатического этикета. Как и в случае с самой Екатериной и ее матерью, и будущая невеста, и ее мать спокойно отнеслись к требованию о смене религии. Довольно предсказуемо, что незадолго до свадьбы ландграф написал из Германии письмо, в котором запрещал дочери переходить в православие. Также предсказуемо он сдался уговорам своей жены. 13 августа 1773 года Вильгельмина приняла православие и стала Натальей Алексеевной. На следующий день она была помолвлена с Павлом и стала великой княгиней.