Вскоре за тем, как двоюродный брат Ягайло - Витовт, бежал из тюрьмы, наступило время проверки боем недавно сформированного польско-литовского союза. Убегая из Вильнюса, Витовт, естественно, мог найти убежище только в соседнем государстве... в Тевтонском ордене. Орден приветствовал любую возможность поддержать распри в стане своих врагов. Крестоносцы подписали мир с Ягайлой в 1383 г. Но когда его двоюродный брат стал королем Польши. Витовт также принял крещение и имя Александр. В 1389 г. Витовт предпринял попытку захватить столицу Литвы Вильнюс. Когда попытка потерпела неудачу, он обратился за помощью к тевтонским рыцарям. Католики из Ордена были готовы пойти на помощь не язычнику Витовту, а католику Александру в борьбе с «фальшивым католиком» Ягайлой. Они заключили сложную дипломатическую сделку с Витовтом перед началом второй осады Вильнюса. В пользу Ордена отходили обширные западные районы Литвы, населенные в основном самогитами (жмудинами), остававшимися в большинстве своем язычниками. Армия Ордена, как всегда, включала многих гостей-крестоносцев, в том числе, Генрих Волинброка (Bolingbroke), графа Дерби, ставшего позже королем Англии Генрихом IV. Он стал самым прославленным английским гостем Ордена, даже если в истории его роль северного крестоносца несколько затенена выдуманным персонажем английского гостя-крестоносца из рассказов Чосера. Летописец обращает внимание, что при осаде Вильнюса Болинброк «имел много прекрасных лучников, принесших существенную пользу». Вторая экспедиция Болинброка 1392 г. хорошо иллюстрирует финансовые выгоды, которые получал Орден от своих гостей-крестоносцев. Свита Генриха состояла более чем из 100 человек, включая шестерых менестрелей, обошед­шихся кошельку Ланкастеров в 4360 фунтов. Большая часть этой суммы ушла в местную прусскую казну через закупку серебра и провианта, найм лодок и подвод.

В ходе кампании 1390 г. Генрих Болинброк выкупил или захватил литовских принцев и затем, очевидно, забрал их в Англию. Рабство было обычной судьбой для пленников, но христианские крестоносцы порабощали только нехристианских пленных. «Святой» Томас Аквинский писал, что «христиане имеют все права владеть рабами-нехристнанами, будь они евреями, язычниками или сарацинами». Крещение Литвы должно было прекратить подобную практику порабощения жертв Ордена. Но она продолжалась, стимулируемая утверждениями тевтонских рыцарей, что христианство Литвы было обманным, а сам факт перехода в христианство был преувеличенным описанием крещения небольшой группки литовцев, разрекламированный для того, чтобы защититься от истинной веры, несомой Орденом.

Несмотря на все старания Болинброка и его английских соратников, два года осады Вильнюса оказались безрезультатными. Ягайло сделал новые предложения Александру Витовту. Они были приняты, и началось подлинное сотрудничество между двоюродными братьями. В результате польско-литовский союз был одним из наиболее успешных политических объединений в средневековой Европе, и его самым большим достижением станет потрясающая победа при Танненберге/Грюнвальде. Однако следует подчеркнуть, что к этому политическому противостоянию Владислав Ягелло, Александр Витовт и Орден пришли со своими целями с трех совершенно разных позиций, и потому «вечное сердечное согласие между Польшей и Литвой» остается только одним из устойчивых мифов того периода.

Тем временем королева Польши Ядвига неожиданно оказалась достаточно весомой политической фигурой, способной вести дипломатические переговоры и успешно защищать интересы дела своего мужа. Ее первым дипломатическим успехом стало 16 - летнее мирное соглашение, заключенное со своим зятем, королем Венгрии Сигизмундом. Союзы с Германией и Богемией еще более подорвали иностранную поддержку Ордена. Переговоры с тевтонскими рыцарями были обречены на провал в основном из-за неразрешимой политической проблемы возвращения польской короне Добжннской области, которую в свое время претендент на польский трон пожертвовал Ордену как гарантию безопасности и плату за поддержку в период политической нестабильности. К сожалению. Ядвига умерла в 1399 г. в возрасте 26 лет, оплаканная всеми поляками как святая.

Существенным прорывом в межгосударственной политике стало подписание формального соглашения между Ягайло и Витовтом в 1401 г., по которому отныне Внтовт считался великим князем Литвы (в западной литературе - «великий герцог»), а Ягайло старшим князем (титулы «старший князь», «великий князь», «большой князь» - были во многом номинальными, поскольку юридически эти старшие князья не имели никаких прав в уделах простых князей, тем более, что рядом «великих» князей татары просто назначали, выдавая фирман в Золотой Орде; но в дипломатическом плане решение с Литвой оказалось удачным, мир между двоюродными братьями удалось установить). По существу, Владислав Ягелло признавался королем Польши и высшим правителем объединения Полыни и Литвы, в то время как Александр Витовт становился его полномочным представителем в Литве. Документ также подтверждал оборонный союз между странами. Достигнутая договоренность была проверена в кровавом будущем грядущего десятилетия.