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