Schon wenige Monate nach Hedwigs Krönung erschien daher eine litauische Gesandtschaft in Krakau und warb für den Großfürsten Jagiello, Olgerds Sohn (1387–1434), 1387 bis 1431 um Hedwig. Durch die Drohungen der polnischen Großen und die Überredungskünste der Geistlichen gezwungen, nahmen Hedwig und ihre Mutter Elisabeth die Werbung an. Die Bedingungen, die die polnischen Magnaten dem Litauer gestellt hatten und die er im Vertrage von Krewo annahm, waren weitgehend genug. Er versprach, sich mit seinem ganzen Hause und Volke taufen zu lassen, die verlorenen Länder dem Reiche auf eigene Kosten wiederzuerobern, die Privilegien zu schützen und zu achten, alle polnischen Gefangenen freizugeben, dem Herzog Wilhelm ein Reugeld von 200 000 Gulden zu zahlen und vor allem seine litauischen und russischen Länder auf ewige Zeiten mit Polen zu vereinigen. Diese Länder aber waren außer Litauen: Weiß- und Schwarzrußland, Polesie, die Ukraine, der größte Teil von Polasie, Wolhynien und Podolien, ein Gebiet, dreimal so groß als Polen.
Der Vertrag, der das große Reich zu einem Vasallenstaat, zu einer polnischen Provinz herabdrückte, war so einseitig und überwiegend für Polen günstig, daß er vielleicht nur aus der Eitelkeit und Selbstsucht Jagiellos, der gern König heißen wollte, ganz zu verstehen ist. Es blieben von den drei großen Staaten des europäischen Ostens nur noch Polen und das Moskowitische Rußland übrig. Zwischen ihnen mußte früher oder später der Kampf um die Vorherrschaft entbrennen.
Am 12. Februar 1386 zog Jagiello in Krakau ein, am 1386 15. wurde er mit einigen seiner Brüder getauft. Pate war Władysław von Oppeln, da der Hochmeister die Übernahme in richtigem Instinkte abgelehnt hatte. Nach dem Paten erhielt er in der Taufe den Namen Władysław, als König seines Namens der Zweite in Polen. Am 18. Februar folgte die Heirat, vierzehn Tage später die Krönung. Doch war Jagiello vorläufig nur Reichsverweser.
Zuerst war der Widerstand Groß-Polens zu brechen. Dann ging es nach Wilna zurück, wo er im Januar 1387 mit seinen Missionaren, meist Franziskanern, die schon länger in Litauen tätig waren, eintraf. Mit Geschenken und Lebensmitteln nicht minder als mit Drohungen wurde das Volk dem Christentum günstig gestimmt. 30 000 Menschen wurden bis zum Frühjahr getauft. (Das gemeine Volk erhielt gruppenweise denselben Namen zur Abkürzung des Verfahrens, ähnlich wie seinerzeit unter Wladimir I. in Kijew.) Den Bojaren, die zum katholischen Christentum übertraten, verlieh der Großfürst-König unterm 20. Februar 1387 eine Anzahl von Freiheiten, 1387 die erkennen lassen, wie absolutistisch bisher die Fürstenmacht im Lande war: sie durften fortan über ihre Güter und ihre Familie verfügen, wurden von der Fron befreit und mit einem geordneten Gerichtsverfahren nach polnischem Muster begabt. Die völlige Gleichstellung mit der polnischen Szlachta bildete von jetzt ab das Ziel des litauischen Adels. In Wilna wurde ein eigenes Bistum für Litauen eingerichtet. Doch ist nicht außer acht zu lassen, daß Samogitien vorläufig beim Heidentum, die russischen Gebietsteile aber bei der griechischen Kirche verblieben. Gleichzeitig regelte Jagiello auch die Verwaltung Litauens, indem er seinen Bruder Skirgiello zum Statthalter einsetzte. Dann kehrte er nach Krakau zurück.
Die ganze osteuropäische Geschichte nahm nunmehr eine andere Wendung. Nachdem Litauen, wenn auch nur oberflächlich, christianisiert worden war, hatte der Deutsche Orden seine Daseinsberechtigung als Orden (doch nur als solcher) verloren. Er durfte in seinen weiteren Kriegszügen gegen die Litauer und in seinen Händeln mit Polen nicht mehr auf die Sympathie des Papstes und auf Zuzug von der westlichen Ritterschaft rechnen. Da ferner bei dieser neuen Personalunion Polen der höher stehende Teil war, stieg sein während der ungarischen Zeit gesunkenes Ansehen wieder gewaltig. Das zeigte sich nicht nur darin, daß die nordrussischen Teilfürsten dem König huldigten und daß Rot-Rußland, von Ludwig zu Ungarn geschlagen, Hedwig den Treueid leistete, sondern noch mehr in dem Übertritt der Hospodare der Moldau (1387), der Walachei (1389), der Wojewoden von Bessarabien (1396) und Siebenbürgen aus dem ungarischen ins polnische Vasallenverhältnis. Damit war nicht nur die polnische Einflußsphäre bis zum Schwarzen Meere ausgedehnt, sondern auch der Handel der galizischen Städte, namentlich Lembergs, gewann unermeßliche Vorteile.
Anderseits kam durch die Vereinigung einer starken griechisch-orthodoxen Bevölkerung mit der Krone Polen ein ganz neues Moment in die Beziehungen der östlichen Welt. Hatten schon die Katholisierungsversuche Ludwigs in Kleinrußland Unzufriedenheit erregt, so mußte die einseitige Bevorzugung der römischen Christen auch in Weiß- und Schwarzrußland Unwillen und Opposition hervorrufen, nicht minder aber in Litauen, wo viele Bojaren und Verwandte Jagiellos orthodox waren, unter anderen Skirgiello. Polen in seinen ursprünglichen Grenzen konnte ebenso wie der Westen auf dem römischen Katholizismus als Staatsreligion basieren, weil es dort fast kein anderes Bekenntnis mehr gab. Nicht so das erweiterte Reich, dessen Festigung schon durch die Mannigfaltigkeit der Nationen erschwert wurde. Eine derartige Politik mußte Konstantinopel sowohl wie später den Moskauer Großfürsten, der sich als den Rechtsnachfolger des Basileus betrachtete, in Gegensatz zu Polen bringen, mußte den Moskowitern einen Stützpunkt innerhalb des Reiches schaffen.
Zunächst äußerten sich die Folgen freilich anders. Witold 1382 bis 1430 (1382–1430), Kejstuts Sohn, der Vetter Jagiellos, ein weitschauender, energischer und tatkräftiger Mann, war Teilfürst von Grodno geworden, strebte aber, dem Vetter sich überlegen fühlend und mit der Unterordnung der Heimat unter Polen unzufrieden, nach der Großfürstenwürde. Er stachelte den Orden gegen Litauen auf, der von 1390–1392 1390 bis 1392 unter Konrad Wallenrod das Land verwüstete. Da gleichzeitig die Litauer im Aufstande waren, sah sich der König veranlaßt, in einer Zusammenkunft zu Ostrow Witold dadurch auf seine Seite zu ziehen, daß er ihn an Stelle Skirgiellos zum Statthalter Litauens machte (1392). Nun war 1392 der Aufstand bald gedämpft, auch der Orden zurückgedrängt. Aber dafür ließ Witold sich 1398 zum Großfürsten ausrufen. 1398 Das bedeutete die Zerreißung der Personalunion, der Grundlage von Jagiellos Königswürde. Offenbar strebte Witold nicht nur dahin, Litauen wieder unabhängig zu machen, sondern er wollte sich auch die Vorherrschaft in Osteuropa sichern. Diesem Zwecke dienten seine Züge gegen die Tataren von der Goldenen Horde, die anfangs glücklich waren, aber 1399 mit der schweren Niederlage an der Worskla 1399 (an der später auch die Schlacht von Poltawa geschlagen wurde) endigten. Bis nach Łuck drangen damals die Scharen Timur Kutluks vor.
Damit waren Witolds Hoffnungen zunichte geworden. Er vertrug sich mit dem König, der ihm die Großfürstenwürde mit der Einschränkung verlieh, daß nach seinem Tod Litauen an die Krone zurückfallen sollte. Witold seinerseits verpflichtete sich zur Unterstützung Polens und leistete den Huldigungseid. Die Bojaren schlossen sich dem an (Wilna 1401). Die polnischen Magnaten hingegen verpflichteten 1401 sich im gleichen Jahre zu Radom, Litauen Beistand zu leisten und nach Jagiellos Tode ohne Litauens Vorwissen keinen König zu wählen. So war der Personalunion von 1386 die förmliche staatsrechtliche Union gefolgt.
Die gegenseitige Unterstützung, die man sich versprochen hatte, sollte zuerst gegen den Deutschen Orden erprobt werden. Die Grenzstreitigkeiten mit den Rittern hatten nämlich ununterbrochen ihren Fortgang genommen, wenn auch bei Lebzeiten Hedwigs, die, wie ihr Vater, eine Freundin des Ordens war, und des friedfertigen Hochmeisters Konrad von Jungingen auf beiden Seiten offene Feindseligkeiten vermieden wurden. Aber Hedwig starb 1399, Konrad 1407. 1399 bis 1407 Nachfolger wurde sein kriegerischer Bruder Ulrich, der sich wohl bewußt war, daß er mit dem nunmehr vereinten Polen und Litauen einen entscheidenden Waffengang auszufechten habe.
1409 kam es zum offenen Bruch, doch vertrug man sich 1409 auf Betreiben König Wenzels von Böhmen noch einmal nach einem kurzen Feldzuge. Den Waffenstillstand benutzte man auf polnischer Seite zu eifrigen Rüstungen. Der Orden war noch immer die erste Militärmacht Europas, die einzige, die innerhalb vierzehn Tagen mobil machen konnte, mit Artillerie vortrefflich ausgerüstet, in andauernden Feldzügen erprobt. Die Polen und Litauer mußten also suchen, durch numerische Übermacht ihre qualitative Minderwertigkeit auszugleichen. Sie warben husitische Söldner unter dem später berühmten Johann Ziska, zogen die Russen heran und verbündeten sich gegen den christlichen Ordensstaat mit den erbitterten Feinden des Christentums, den Tataren. Die Hilferufe der Ritter verhallten vergebens. Nur geringer Zuzug ward ihnen aus Deutschland, das von Wahlstreitigkeiten und Konzilvorbereitungen zu sehr in Anspruch genommen war, als daß es für den Grenzposten im Nordosten Interesse haben konnte.