На момент приезда послов Генриха герцогом Клевским был уже Вильгельм — сын недавно скончавшегося Иоганна. Он имел весьма строгие понятия о женской скромности, и, когда принцесс официально представили послам, на них были настолько громоздкие платья и плотные головные уборы, а лица скрывались под безобразными вуалями, что тем не удалось разглядеть внешность девушек. Музыка и танцы также были запрещены, к огорчению Генриха, поэтому таланты потенциальных невест в этих областях также остались неизвестны.
После доклада об этом Кромвелю тот немедля отправил Ганса Гольбейна написать портреты сестер, а королю сообщил: «Все восхваляют красоту леди Анны, так как и лицо, и фигура ее восхитительны. Она далеко превосходит герцогиню Саксонскую, как золотое солнце превосходит серебряную луну. Все восхваляют ее добродетель и честность вместе со скромностью, которая ясно видна в ее наружности».
Вильгельм Клевский поначалу отнесся к этой затее без всякого энтузиазма. Однако он быстро изменил свое мнение, когда узнал, что Генрих готов жениться на одной из его сестер, не требуя приданого, но при условии, что ему понравится портрет. Вполне возможно, что Кромвель, предложивший этот брак и рассчитывавший таким образом упрочить свое положение, дал художнику указание изобразить Анну в самом выгодном свете. Но все получилось: Генрих настолько влюбился в портрет, что велел продолжить переговоры, хотя и несколько приуныл, узнав, что Анна не владеет ни иностранными языками, ни светскими талантами. Тем не менее послы заверили его, что принцесса умна и способна, поэтому она вполне в состоянии быстро выучить английский язык.
Услышав о готовившемся брачном союзе, последователи протестантизма в Англии и за ее пределами обрадовались, полагая, что под влиянием новой супруги Генрих упрочит положение этой религии в королевстве. Но король отнюдь не собирался потакать протестантам и рассчитывал на то, что в замужестве Анна примет католическую веру. Впоследствии Анна действительно не принимала никакого участия в протестантских движениях, а кроме того, вследствие дружбы с дочерью Генриха — принцессой Марией, стала католичкой.
4 сентября 1539 года был подписан брачный договор, и невеста отправилась в путешествие к берегам туманного Альбиона. В Англию вели два пути: один — по морю, а другой — по суше через порт Кале, откуда уже за день можно было достичь Англии. Поскольку первый отвергли из-за опасений, что длительное морское путешествие скажется на фигуре принцессы, и она станет непривлекательной для будущего мужа (в последние годы Генрих предпочитал полных женщин), то выбрали путь по суше.
Если бы в канун 1540 года кто-то из жителей графства Кент выглянул на улицу, он увидел бы довольно необычную картину: кортеж всадников, закутанных в дорогие меха, стремглав мчался по дороге в Рочестер, в епископский дворец. Король Генрих так желал увидеть невесту, что решил предпринять этот неофициальный визит. Там, в Рочестере, и состоялось первое знакомство жениха и невесты. На протяжении всей встречи король и принцесса оставались наедине, причем жених еле скрывал свое разочарование. Покидая Анну, Генрих сказал: «Я не вижу ничего из того, что было представлено мне на картинах и в донесениях. Мне стыдно, что люди так ее восхваляли, — и я ее совсем не люблю!»
После возвращения в Гринвич король сразу же обрушил гнев на Кромвеля, отозвавшись о невесте как о «здоровенной фламандской кобыле». Ведь если Гольбейна, по его мнению, можно было простить (он художник и многое видит иначе, чем остальные люди), то как можно простить министра, организовавшего этот брак? Кромвель же в свою очередь попытался возложить всю вину на главу делегации Саутгемптона: «Когда адмирал обнаружил, что принцесса отличается от портрета и описаний, ему следовало задержать ее в Кале, а самому уведомить короля, что она не так хороша, как представлялось».
Неизвестно, что именно особенно не понравилось Генриху в невесте, но в течение нескольких оставшихся до венчания дней юристы короля пытались найти способ расторгнуть помолвку. Однако Кромвель все-таки убедил Генриха, что брак уже практически заключен и было бы крайне неосмотрительно отправить принцессу назад. Такое оскорбление грозило бы неприятностями с братом Анны, а кроме того, оставляло Англию без союзников в случае нападения французов или испанцев.
Их свадьба состоялась 6 января 1540 года в королевском дворце Бэлла Корт в Гринвиче. Генрих в этот день произнес такую фразу: «Милорды, если бы не мир и мое государство, я не сделал бы того, что я должен сделать, ни за что на земле». И многозначительно посмотрел на Кромвеля…