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