Одновременно в состав Польши была возвращена ранее занятая венграми Галицкая земля. Но со временем в отношениях между странами возникли проблемы. Польская знать при поддержке Владислава рассматривала Литву как владение, зависимое от Короны. Все документы, касавшиеся Великого княжества Литовского, исходили из польской королевской канцелярии, а русско-литовские князья должны были приносить присягу на верность Владиславу, Ядвиге и Короне королевства Польского. Тогда же в Вильно появились польский наместник и гарнизон. Всё это вызывало недовольство литовского боярства. Оно стало переходить на сторону Витовта, которого в борьбе с Владиславом поддерживал Тевтонский орден. Положение было опасным, т.к. крестоносцы, несмотря на крещение литовцев, продолжали военные походы на Литву, их войска неоднократно подходили к Вильно. Владислав был вынужден пойти на уступки. По соглашению, заключённому в Острове 4 августа 1392 г., Витовту были возвращены владения отца, ему передавалось управление Великим княжеством Литовским. Титул «великий князь» и верховную власть над Литвой Владислав сохранил за собой. В дальнейшем в отношениях между Польшей и Литвой, Владиславом и Витовтом, бывали трения, подчас достаточно серьёзные (как, например, в 1398 г., когда в ответ на требования денежных выплат в знак зависимости литовские бояре на острове Салин провозгласили Витовта «королём Литвы»), но связи оказались достаточно устойчивыми. Они укрепились в 1401 г., когда Витовт получил от Владислава Великое княжество Литовское в пожизненное держание, а также великокняжеский титул. Однако Владислав сохранял за собой верховную власть, во время регулярных объездов страны каждую зиму проводил в Литве. Прочность отношений между государствами, согласие литовского боярства признать зависимость своей страны от Польши были связаны с общей заинтересованностью знати обоих государств в борьбе с экспансией Тевтонского ордена. Правда, в конце 1390 гг. крестоносцы заключили мир с Литвой, но во время предшествовавших смут ими была захвачена Жямайтия. Эта победа позволила соединить прусские и ливонские владения Ордена и оттеснить Литву от Балтийского моря. Ещё раньше крестоносцы захватили Восточное Поморье, закрыв Польше выход к Балтийскому морю. Кроме того, литовское боярство рассчитывало с польской помощью расширить границы на востоке. Эту задачу Владислав и Витовт в начале XV в. сочли даже более важной, чем борьба с крестоносцами. По миру, заключённому в мае 1404 г., они признали права Ордена на находившиеся в его владении земли в обмен на обещание военной помощи в походах на восток. Когда Витовт в 1406–1408 гг. трижды предпринимал походы против великого князя Василия I Дмитриевича, то получал военную помощь от Ордена. Владислав также высылал против русских значительные отряды во главе с первыми вельможами Короны. Лишь когда эти походы оказались безуспешными, а в Жямайтии началось восстание против крестоносцев, Владислав и Витовт сосредоточили силы на борьбе с Орденом. Владислав командовал соединённым польско-литовским войском, которое в битве под Грюнвальдом 15 июля 1410 г. разгромило войско крестоносцев. Ордену был нанесён удар, от которого он уже не смог оправиться.