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