Когда принцессе исполнилось семнадцать лет, в далекой России начали искать невесту для цесаревича Павла. Как и обычно, из разных концов Европы советники отбирали принцесс и ко двору доставляли портреты. Активизировался и Фридрих II, желая пристроить одну из гессенских принцесс, что позволило бы ему держать в России своего человека. В идеальном для него варианте было бы замечательно, если бы наследник прусского престола, его племянник, и российский наследник Павел женились бы на родных сестрах. Портреты принцесс и их описания были отправлены в Россию.
Портрет Вильгельмины пришелся по вкусу и императрице, и жениху. Павлу Петровичу уже тогда казалось, что у девушки не может быть никаких недостатков. Екатерина же была настроена более рационально. В письме к посланнику, который занимался поисками невесты, господину Ассебургу, императрица писала, что «совершенства, как мне известно, в мире не существует». Нужна была личная встреча, которую назначили на лето 1773 года.
Ландграфиню Каролину вместе с дочерьми пригласили в Россию. Всю поездку оплатила императрица. Корабль с принцессами поручили сопровождать близкому другу Павла Петровича, графу Андрею Разумовскому. Неизвестно доподлинно, действительно ли между Вильгельминой и молодым графом тогда завязались отношения, которые вскрылись уже после смерти принцессы. Многим петербургским красавицам он разбивал сердца: красивый, обаятельный, всегда с иголочки одетый (порой для этого он влезал в огромные долги).
Сопровождающим фрегаты Екатериной Второй было дано указание — отмечать любые особенности характера, манер и поведения принцесс. Ландграфиня же с девушками тоже должны были провести серьезную работу — выучить указания российской самодержицы о том, как они должны себя вести, если кто-то из них станет великой княгиней. Например, отмечалось, что нельзя слушать сплетни и наветы, копить долги, а на людях нужно держаться с достоинством; развлечения выбирать согласно статусу, больше читать и заниматься музыкой.
15 июня фрегаты прибыли в Ревель, где их встретил фаворит императрицы граф Орлов. Он пообещал, что за обедом гостьи познакомятся с придворными дамами. Однако каково было удивление ландграфини и ее дочерей, когда пожаловала сама Екатерина! Это было нарушением всех согласованных графиков, но императрица пожелала познакомиться с прибывшими немками в спокойной неформальной обстановке. Гостьи ей понравились: ландграфиня была интересной собеседницей с «большими достоинствами», а все три принцессы оказались милыми девушками. Старшая, Амалия, произвела впечатление слишком скромной, младшая, Луиза, — очень умной. В Вильгельмине же императрица отметила и красоту, и ум. Конечно, она не забыла наблюдения своего посланника, который писал о честолюбии, склонности к интригам и амбициозности, но дело оставалось за Павлом.
И он был очарован принцессой.
Цесаревича, конечно, понять можно — в прелестной Вильгельмине он видел возможность обрести верную спутницу; семью, которой ему так не хватало. Как известно, цесаревич чувствовал себя очень одиноким, с матерью отношения не складывались. Ему нужен был близкий человек.
В столице шла череда балов и маскарадов в честь прибывших гостей. Наконец через два месяца официальный выбор был сделан: принцессу Вильгельмину выбрали в жены для Павла Петровича. После этого она принялась изучать основы православия, а 15 августа приняла его под именем Натальи Алексеевны. На следующий день всем было объявлено о помолвке. Свадьбу назначили на конец сентября.
Павел не отходил от своей нареченной, а будущая свекровь одаривала ее драгоценностями: бриллиантовое ожерелье, кольцо и серьги в честь помолвки, ожерелья из изумрудов и бриллиантов, серьги и подвески позже. Сестры Натальи Алексеевны тоже не были обделены — всем вручили Орден святой Екатерины, который считался высшей наградой для женщин в Российской империи.
Гуляния в честь свадьбы продолжались целый месяц. В день бракосочетания невесту облачили в наряд такой пышности, какой она ранее и не представляла — парчовое платье было усыпано бриллиантами. Блистала и самодержица, одетая в платье из атласа и горностаевую мантию. Гуляния проводились как для аристократии, так и для простого народа. После них мать и сестры Натальи отбыли домой, а у цесаревича с женой началась семейная жизнь.
Все замечали, как Павел Петрович, ранее замкнутый, так походивший на отца, преобразился. Он не оставлял свою жену, проявлял внимание и ухаживал за ней. Только вот Наталья Алексеевна очень холодно принимала ухаживания мужа. Был ли в ее сердце Разумовский или она просто не полюбила Павла? Так или иначе, в своих письмах отцу она даже словом не упоминала о своем супруге или своих чувствах к нему. Заметили это и окружающие — казалось, что княгиня просто терпит цесаревича.