Спустя несколько месяцев царь отправил в Данию послами окольничего Проестева и дьяка Патрикеева все еще по поводу торгового договора, а вместе и с поручением начать сватовство. Но так как послы, сообразуясь со своим наказом, прямо поставили требование о крещении принца в православную веру, то напрасно они раздавали деньги и соболей; получив отказ, они воротились без успеха. В Москве этот неуспех приписали неумению послов вести переговоры и обвинили в нерадении, за что подвергли их опале. Тогда сие щекотливое дело передали известному Петру Марселису и отправили его в Данию, снабдив значительным количеством соболей и денег для подарков влиятельным лицам. Марселис искусно повел переговоры о браке; причем по вопросу о перемене веры отделывался неопределенными обещаниями. А так как Христиан IV в то время был угрожаем войной со стороны Швеции, то он надеялся в лице московского царя приобрести доброго союзника против шведов; а потому охотно согласился отпустить сына в Москву, только желал обеспечить его предварительными условиями, скрепленными царской грамотой. В числе этих условий главное место занимали: свобода вероисповедания для королевича и его свиты, положение королевича в России такое, чтобы кроме царя и царевича Алексея никого не было выше Вальдемара и чтобы обещанные ему во владение города Суздаль и Ярославль с уездами навсегда оставались в его потомстве.
Марселис с торжеством воротился в Москву и, конечно, не преминул выхлопотать себе разные награды и льготы. Ему же поручено было отвезти в Данию ответную царскую грамоту, составленную в смысле указанных условий, но не имевшую характера окончательного договора. Такой договор должны были заключить с боярами великие датские послы, имевшие прибыть вместе с принцем. Христиан, так же как и царь, был доволен услугами Марселиса и наградил его дворянским достоинством. Осенью 1643 года Вальдемар вместе с новым посольством отправился в Москву уже в качестве жениха Ирины Михайловны под именем графа Шлезвиг-Голштинского, имея при себе большую свиту; вместе со свитой датских послов число ее простиралось свыше 300 человек. Избегая столкновения со шведами, Вальдемар, по приглашению короля Владислава, ехал через Польшу и Литву, где ему оказали большие почести.
В Пскове, Новгороде и Твери по распоряжению из Москвы Вальдемару и его свите устроены были торжественные встречи. Вперед его приехал в столицу главный сват, Петр Марселис, уже в качестве посла от датского короля и сына его, графа Шлезвиг-Голштинского, и удостоен царского приема с обычными посольскими обрядами. В январе 1644 года прибыл наконец сам Вальдемар с датскими послами. За Тверскими воротами его встретили царские стольники, стряпчие, дворяне и жильцы, во главе с боярином М. М. Салтыковым, который говорил ему приветственную речь. Королевича поместили в бывшем доме царя Бориса Годунова; дом этот находился не только в близком соседстве с царским дворцом, но и соединялся с ним крытым ходом. Начался ряд пышных приемов и царских званых обедов. Царь Михаил и царевич Алексей всеми мерами ласкали жениха и щедро дарили его сороками соболей, дорогими кубками, коврами, золотой и серебряной парчой и тому подобное. Мало того, они иногда помянутым крытым ходом навещали принца и запросто с ним беседовали. Царица Евдокия, со своей стороны, дарила нареченному зятю куски ситца и дюжины полотенец. Патриарх Иосиф тоже посетил принца и поднес ему дары с пожеланием счастия и благополучия в предстоящем супружестве.
Посреди этих праздников и ласкательств граф Вальдемар в одно прекрасное утро немало был озадачен, когда к нему явился от патриарха служилый иноземец (Францбеков) и предложил сначала креститься в православную веру, а затем уже приступить к брачному обряду. Дело в том, что Смутная эпоха и насилия, претерпенные русскими от ляхов, окончательно обострили отношения православия к латинству. И прежде при переходе католика в православие требовалось часто не одно миропомазание, но также и крещение с троекратным погружением. А церковный собор 1620 года, созванный и руководимый патриархом Филаретом, как известно, издал решительное постановление о перекрещивании латинян и прочих западных иноверцев для присоединения их к православной вере.