W 1385 roku w Krewie Polska i Litwa zjednoczyły swoje siły tworząc unię. Różne czynniki zarówno polityczne jak i gospodarcze doprowadziły do unii obu państw (zobacz więcej). Jednym z nich było zahamowanie krzyżackich najazdów na Litwę, drugim odzyskanie ziem utraconych przez Polskę na rzecz Krzyżaków. Zjednoczone siły Polski i Litwy były w stanie przeciwstawić się sile zakonu. Krzyżacy nie uznawali chrystianizacji Litwy, ponieważ chrześcijańska Litwa stawiała znak zapytania nad sensem istnienia Państwa Zakonnego nad Bałtykiem. Dlatego Zakon Krzyżacki rozpoczął w Europie akcję propagandową skierowaną przeciwko Polsce i Litwie. Krzyżacy oskarżali Polskę o zawarcie sojuszu z poganami skierowanego przeciw chrześcijanom. Strona polska nie pozostała bierna rozpoczynając szeroko zakrojoną misję dyplomatyczną na dworach Europy i kurii papieskiej. Z kolei Krzyżacy starali się wykorzystać nieporozumienia między Jagiełłą i jego stryjecznym bratem Witoldem. Zakon poparł Witolda, który zbiegł do Prus, a następnie ruszył z Krzyżakami na Wilno i Troki. Jagiełło jednak odparł krzyżacki atak z roku 1390. Po dwóch latach bracia stryjeczni pogodzili się a Witold został namiestnikiem całej Litwy. Niedługo po tym Witold przygotowując się do walki z Tatarami zawarł pokój (1398) z Krzyżakami, bez porozumienia z Władysławem Jagiełłą oddając im Żmudź. Był to kolejny sukces Krzyżaków, po zajęciu w 1392 roku Ziemi Dobrzyńskiej. Witold zmienił swoją politykę po klęsce w bitwie z Tatarami. Znów doszło do zbliżenia wielkiego księcia litewskiego z królem Polski. Zaowocowało to ugodą w Wilnie i Radomiu oraz hołdem Witolda,  który został dożywotnim księciem Litwy. W tym samym czasie na Żmudzi wybuchło powstanie przeciw Krzyżakom. W 1404 roku zakon zajęty walką o Gotlandię zawarł z Polską układ w Raciążu oddając za cenę wykupu Ziemię Dobrzyńską, natomiast Litwa zajęta jednoczeniem ziem ruskich ponownie zrzekła się Żmudzi.