Ягайло, узнавший от доброжелателей о тайной миссии визитера, встретил его необычайно ласково и с почетом. Богато одаренный слуга сообщил королеве, что в теле князя нет изъянов, он строен, среднего роста, приятной наружности, в обхождении важен и в целом смотрится государем. Это успокоило Ядвигу, и она согласилась принять жениха.
В следующем году состоялась их свадьба, важное событие объединило два народа в одно государство. Среди наиболее почетных гостей был и Витовт с семьей. В Кракове юная Софья познакомилась со всем цветом польского и литовского общества. Несомненно, она была одной из самых красивых девушек и весьма завидной невестой. Многие паны и князья стали просить у Витовта ее руки, но все получали отказ — с московским княжичем, будущим государем Руси, никто сравниться не мог.
Вскоре Софья убедилась в том, что отец исключительно правильно выбрал ей жениха. Дружба нового польского короля с двоюродным братом продолжалась очень недолго. Поводов для ссоры оказалось предостаточно. Во-первых. Ягайло отдал великое Литовское княжение своему брату Скиргайло, а не Витовту. Во-вторых, словно бросая вызов своемуродственнику, тот перенес литовскую столицу в Троки и начал там насильно распространять католичество. Местное население, когда-то подчинявшееся Витовту, вынуждено было бежать в леса.
Витовт переехал в Гродно, но новый великий князь Литовский Скиргайло и Ягайло не оставляли его в покое. Постоянные ссоры вынудили гордого воина вновь отправиться в Пруссию и поступить на службу к магистру.
Для Софьи очередная полоса скитаний оказалась очень короткой. Зимой 1390 года в Мариенбург, где тогда проживала семья Витовта. приехало московское посольство. Бояре Александр Поле, Белеут и Селиван били челом литовскому князю и напомнили об обещании отдать дочь Софью за великого князя Московского Василия Дмитриевича. Витовт не стал возражать. Он знал, что некогда гостивший у него русский княжич уже правит самостоятельно большим и богатым княжеством и среди остальных князей считается старшим.
Наверняка Софье было страшно ехать в далекую и незнакомую страну, но она помнила о встрече с Василием и своему слову изменять не хотела. Кроме того, Софья стремилась обрести свой дом, стать государыней и повелевать тысячами подданных — властолюбивыми мечтаниями она пошла в отца.
Поездка предстояла долгая и трудная — через враждующие друг с другом страны. Сопровождать княжну вызвались дядя Иван Ольгердович и некоторые представители литовской знати.
Летописи не сохранили нам сведений о том, как проходило путешествие юной Софьи. Известно лишь, что новгородцы встретили ее с большой честью, для отдыха поселили на Городище, где располагалась княжеская резиденция, устроили пир.
Затем Софью приветствовал сын серпуховского князя Андрей Владимирович, потом, на подступах к столице, брат будущего мужа Юрий Дмитриевич и, наконец, 30 декабря в воротах Кремля — митрополит Киприан со всем высшим духовенством, бояре и знать. За пышной церемонией наблюдали тысячи москвичей, желавших увидеть свою новую государыню.
Киприан проводил великокняжескую невесту в Успенский собор на торжественный молебен. После него Софья встретилась с будущей свекровью, великой княгиней Евдокией Дмитриевной, в чьих покоях до свадьбы и поселилась.
Точно не известно, была ли Софья православной, ведь ее отец с легкостью менял веру ради политической выгоды. Возможно, ей пришлось вновь креститься по православному обряду, поскольку, по данным летописи, перед свадьбой она стала называться Анастасией, но в быту, видимо, сохранила прежнее имя.
Со свадьбой затягивать не стали. 9 января 1391 года в Успенском соборе митрополит Киприан благословил молодых, и они были венчаны священником. На свадьбе присутствовали все братья и другие родственники великого князя, а также многочисленная русская и литовская знать. Пиры продолжались несколько дней.
После свадебных торжеств Софье Витовтовне пришлось принимать бразды правления большим великокняжеским домом в свои руки. До этого хозяйственными вопросами занималась Евдокия Дмитриевна. В ее ведении оказались пряхи, швеи, вышивальщицы — мастерицы по изготовлению одежды и постельного белья для всей семьи Василия Дмитриевича. Кроме того, следовало заботиться о красоте и уюте дворца и надзирать за поварней. Правда, все эти обязанности княгине предстояло выполнять не лично, а с помощью многочисленной дворни.
Для молодой супруги Василий Дмитриевич обновил некоторые помещения кремлевского дворца. К набережному терему были пристроены столовая-гридня и повалуша — большая палата с расписными стенами. В ней Софья могла встречаться с боярынями и устраивать семейные праздники.