Весной 1773 года три гессенские принцессы и их мать были приглашены в Россию. Сначала они остановились в Берлине, как и в случае с Софией Ангальт-Цербстской тридцать один год назад, Фридрих напомнил, что они не должны забывать о своем немецком происхождении. К концу июня четыре русских корабля прибыли в Любек и повезли немецких гостей по Балтике. Фрегатом, на котором находились три молодые женщины и их мать, командовал лучший друг Павла, Андрей Разумовский, сын друга Екатерины – Кирилла Разумовского. Андрей был очарован средней дочерью, Вильгельминой, она также ответила ему взаимностью.

В Санкт-Петербурге Павлу понадобилось только два дня, чтобы сделать свой выбор, и он совпал с выбором Андрея Разумовского – это была принцесса Вильгельмина. К сожалению, реакция девушки на невысокого, странного молодого человека, предназначенного ей в мужья, была лишена энтузиазма. Екатерина обратила внимание на ее колебания, заметила это и ее мать. Тем не менее дальнейшие события развивались в соответствии с требованиями дипломатического этикета. Как и в случае с самой Екатериной и ее матерью, и будущая невеста, и ее мать спокойно отнеслись к требованию о смене религии. Довольно предсказуемо, что незадолго до свадьбы ландграф написал из Германии письмо, в котором запрещал дочери переходить в православие. Также предсказуемо он сдался уговорам своей жены. 13 августа 1773 года Вильгельмина приняла православие и стала Натальей Алексеевной. На следующий день она была помолвлена с Павлом и стала великой княгиней.

В конце лета стали устраивать банкеты, балы и пикники, на которых Екатерина с удовольствием проводила время в компании ландграфини – энергичной женщины, дружившей с Гёте. Князь Орлов пригласил трех принцесс, их мать, Екатерину и двор в Гатчину, где дал пышный прием: пятьсот гостей обедали на золотых блюдах и севрском фарфоре. Орлов, надеясь вызвать раздражение императрицы, приехавшей в компании нового фаворита, Васильчикова, тут же начал флиртовать с Луизой, самой юной из принцесс. Прусский министр в своем письме в Берлин описывал «необычайное внимание, которое князь Орлов оказывал ландграфине, и ту свободу в обращении, с которой он обращался с принцессами, особенно самой младшей из них».

Свадьба девятнадцатилетнего Павла и семнадцатилетней Натальи произошла 29 сентября 1773 года. За ней последовали десять дней придворных балов, театральных представлений и маскарадов, во время которых на улицах люди пили бесплатное пиво, ели пироги с мясом и смотрели фейерверки, вспыхивавшие в небе над Петропавловской крепостью. Павел торжествовал: казалось, он был на пороге новой жизни и обретал свободу. Наталья утешала себя тем, что Андрей Разумовский теперь всегда будет подле нее.