Поиски продолжились, и в 1795 году с секретной миссией по правящим дворам Европы отправился генерал Андрей Яковлевич Будберг, чтобы из огромного списка лично отобрать кандидаток в невесты юного князя. Однако по пути генерал заболел и вынужденно остановился в Кобурге, где обратился к знакомому врачу — барону Христиану-Фридриху Штокмару. Тот, узнав о цели визита генерала, обратил его внимание на дочерей герцога Саксен-Кобург-Заальфельдского. Подлечившись, Будберг больше никуда не поехал и сообщил в Петербург, что справился с заданием.
Екатерина II сначала устроила небольшую проверку, а затем дала согласие, позволив Будбергу «раскрыть карты» перед герцогиней Августой. Та, узнав, что одна из ее дочерей может стать женой русского великого князя, несказанно обрадовалась: она понимала всю выгоду этого брака для своего маленького герцогства.
Итак, 6 октября 1795 года 14-летняя Юлианна со своими старшими сестрами Софией (1778–1835) и Антуанеттой (1779–1824), а также матерью Августой прибыла в Петербург для смотрин в качестве невесты младшего внука императрицы — шестнадцатилетнего Константина. Екатерина II писала: «Наследная принцесса Саксен-Кобургская — прекрасная, достойная уважения женщина, дочки у нее хорошенькие. Жаль, что наш жених должен выбрать только одну, хорошо бы оставить всех трех. Но, кажется, наш Парис отдаст яблоко младшей: вот увидите, что он предпочтет сестрам Юлию… действительно, шалунья Юлия лучше всех».
Свадьба состоялась 26 февраля 1796 года, а за три недели до этого Юлианна Генриетта приняла православие и стала Анной Федоровной.
Первое время юная чета казалась счастливой, но влюбленность принца быстро прошла, а его вспыльчивый и сумасбродный характер вскоре сделал семейную жизнь пары невыносимой. Неуемная страсть князя ко всему военному, переходящая в солдафонство, отразилась на домашнем укладе. Нередко его нежность сменялась грубостью и оскорбительным отношением к юной супруге. Однажды, например, он посадил Анну Федоровну в одну из огромных ваз в Мраморном дворце и начал по ней стрелять. Конечно, терпеть характер мужа и его наглые выходки княгине становилось все труднее. К сожалению, она не могла рассчитывать на поддержку императора Павла, ведь невесту Константину выбирал не он, а ненавидимая им мать. При этом, взрослея в столь непростых условиях, Анна Федоровна расцветала, становясь все привлекательнее. Вскоре Константин начал ее ревновать: он запрещал ей покидать императорские покои, а если она все же выходила, то тотчас являлся и уводил ее прочь от всех. Графиня В. Н. Головина, говорившая в свое время, что Константин вовсе не желал жениться и его просто принудили к этому, вспоминала: «Анне Федоровне тяжело жилось от невозможного характера, которого никто не мог обуздать. Его грубые выходки, отсутствие всякого такта превращали супружескую жизнь в настоящую каторгу…»
Но через три года после замужества, в 1799 году, Анна Федоровна покинула Россию, чтобы подлечиться, и не захотела возвращаться. Сначала она приехала к родным в Кобург, но не нашла у них понимания, поскольку они заботились о репутации семьи и финансовом положении не только Анны Федоровны, но и своем собственном. Из Кобурга она уехала лечиться на воды с твердым намерением не возвращаться к мужу. В Петербурге узнали о ее планах. Повинуясь давлению императорской и собственной семьи, Анна Федоровна была вынуждена вернуться в Россию. В октябре 1799 года планировались свадьбы сестер ее мужа Александры и Елены, и великая княгиня должна была на них присутствовать.
Только после убийства императора Павла в 1801 году Анна Федоровна смогла осуществить задуманное. Вскоре ей сообщили, что герцогиня Августа тяжело заболела. Царственный деверь княгини, император Александр I, хорошо относившийся к невестке, разрешил ей навестить мать. Муж, Константин Павлович, тоже не был против — у него начинался очередной роман. Анна Федоровна уехала в Кобург, чтобы больше не вернуться в Россию. Почти сразу же она начала вести с мужем переговоры о разводе. Константин Павлович не возражал.
Однако в 1803 году против развода выступила императрица Мария Федоровна. Она заявила, что развод навредит репутации великой княгини, хотя на самом деле боялась повторного морганатического брака Константина Павловича.
В 1814 году, во время антинаполеоновской кампании русских войск во Франции, Константин Павлович навестил свою жену. Несмотря на желание императора Александра примирить супругов, Анна Федоровна решительно отказалась возвращаться в Россию к мужу.
Таким образом, после бегства великой княгини из России супруги официально находились в браке еще девятнадцать лет, хотя обе стороны просили о разводе. Только в марте 1820 года, когда встал вопрос о второй женитьбе Константина, брак был расторгнут официально — манифестом Александра I. Спустя еще два года последовал тайный отказ цесаревича от прав на престол, а еще через три года произошли хорошо известные события декабря 1825 года, когда для всех цесаревич Константин стал императором Константином I.