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

Ясно, что такой раздел аристократии по религиозному принципу должен был привести к взаимной вражде и, в конце концов, к войне. Понимал ли это Витовт? Видел ли, что поляки мечтали после его смерти присоединить Великое Княжество к Польше? Надеялся перехитрить Ягайлу и его советников?

Произошла и административная реформа. Великое Княжество Литовское по примеру Польского Королевства было разделено на воеводства: Виленское и Трокское. Там вводились должности воеводы и его наместника, каштеляна, которые могли занимать только католики. В остальных землях Великого Княжества Литовского правили великокняжеские наместники, которые управляли на основании уставных грамот, декларировавших принцип: старины не рушить и нового не вводить.

Некоторые Гедиминовичи сохранили свои удельные княжества: Олельковичи — Слуцкое, Сангушки — Кобринское, Евнутовичи — Заславское, Лугвеновичи — Мстиславское, брат Витовта Сигизмунд — Стародубское.

Но они уже не влияли, как раньше, на политическую жизнь в государстве. Витовт стал опираться на панов и шляхту. Молодая аристократия с энтузиазмом помогала ему в управлении государством.

После подписания Городельской унии Витовт и Ягайло отправились в Жемайтию, чтобы крестить ее и установить там великокняжеское правление. Несмотря на уговоры, подарки, подкуп старейшин, жемайты упорно держались язычества. Тогда Витовт силой начал насаждать христианство. Высекались священные дубровы, уничтожались капища. В огне горели идолы языческих богов. Жемайты вынуждены были подчиниться. «Мы узнали, яснейший король Ягайло и светлейший великий князь Витовт, государь наш, что наши боги слабые и сброшены вашим Богом, покидаем их и к Богу вашему, как сильнейшему, пристаем», — подчинились жемайты новому Богу. Их крестили, как в свое время литвинов. Сгоняли толпы людей, разделяли их на мужчин и женщин и огулом окропляли святой водой. Каждой группе давали одно на всех крестное имя. При таком крещении «христианин» оставался в душе язычником и по-прежнему поклонялся идолам, но только тайно.

В 1418 году жемайты восстанут и с ненавистью расправятся с великокняжеской администрацией, разрушат и сожгут костелы. Витовт пошлет на усмирение «лиходеев» войско во главе с жемайтским старостой Кезгайлой. Он «хватал, бил всех тех, кто это делал», как сообщал Витовт Ордену. И сам великий князь придет на усмирение восставших и жестоко покарает их, за что получит прозвище «кровопийца» и «кровавый мясник».

Папа Мартин V учредил в Жемайтии епископство с приходами в Меденках, Ковно, Крожах, Ариогале, Водукяе, Утянах и Ворнях.

Как отметил летописец «Хроники Быховца», «окрестил он всю землю Завельскую, костелов много поставил; поэтому и назвали Витовта вторым апостолом Божиим, что он из упорного язычества обратил те земли в веру христианскую». За время правления Витовта в ВКЛ было построено более 30 костелов, в том числе в Берестье, Вильно, Витебске, Волковыске, Городно, Дубинках, Ковно, Новогородке, Ошмянах, Пинске, Троках, Утянах и других местах.

Со времени крещения Жемайтии начинается политическое возвышение Витовта. Он умело использует напряженное положение в Европе, чтобы достичь своих целей. В отношении Орды Витовт противопоставляет одних ханов другим, не давая никому из них возвыситься. То он оружием своего ставленника Улуг-Мухамеда борется с ханами Худайтом и Бораком, пришедшими со своими ордами в волжские и донские степи из Средней Азии, то уже против Улуг-Мухамеда поддержал крымского хана Довлей-Берды.

Поэтому в Европе Витовта воспринимали как «короля сарацинов». И дружбы этого короля ищут европейские монархи. Император Священной Римской империи Сигизмунд обещает ему королевскую корону. Чехи в 1422 году выбирают Витовта своим королем, и в Праге правит его наместник князь Сигизмунд Корибутович, Признают власть Витовта и русские князья. «Верность и послушание» Витовту выразили рязанский, переяславский, пронский, новосильский, одоевский, воротынский, кашинский и тверской князья. Князья поклялись служить Витовту верно, без хитрости и быть с ним всегда заодно. Летом 1427 года Витовт объехал их княжества и принял князей под свою власть. В свою очередь Витовт поклялся защищать их «от всякого», не вторгаться в их вотчину.

Вот как описывает Витовт свое путешествие в письме от 15 августа 1427 года великому магистру Ордена: «Нас встречали великие герцоги с русских земель, которые тут называются великими князьями, рязанский, переяславский, пронский, новосильский, одоевский, воротынский... и обещали нам верность и послушание. Принимали нас везде с великим почетом и дарили золото, серебро, коней, сабли... Как мы сообщали, наша дочка, великая княгиня Московская, сама недавно посетила нас и вместе со своим сыном, землями и людьми передалась под нашу корону». Таким образом, власть Витовта признала почти «вся Русская земля», как сообщает летопись.

И Витовт не преувеличивал, когда говорил об оказанном ему большом почете. Орденский шпион и одновременно придворный шут Витовта Гейне доносил великому магистру: «Знайте еще, что у великого князя были и посольства из Великого Новгорода, Москвы, Смоленска и постоянно все приезжают к нему послы: от татарского хана, от турецкого султана и от многих других христианских и нехристианских князей. Приезжают они с богатыми подарками, — трудно было бы их всех описать, расскажу о том устно, когда возвращусь». Витовт, не имея королевской короны, имел власть и почет больше, чем у иного европейского короля того времени.

Со своей стороны Витовт обязался защищать своих вассалов от врагов и честно держал клятву. Когда в 1425 году татарский князь Кундат пришел к Одоеву с ратью на князя Юрия Романовича Одоевского, то Витовт срочно выслал на помощь дружины шесть князей во главе с братьями Иваном Бабой и Путятой Друцким. Они вместе с Юрием Романовичем, как сообщает летопись, «царя Кундада прогониша, и силу его побиша». По этому поводу Витовт писал великому магистру Ордена Паулю Росдорфу: «Это событие нас очень обрадовало, что милостивый Бог даровал нам и нашим людям такое счастье, что они одержали такую блестящую победу, которой еще никогда не было, хоть и часто происходили битвы».