После смерти Миндовга в 1263 году «во всей земле Литовской и в Жемойти» правил жемайтский князь Тренята. Новый правитель сразу заявил о своей силе и дал понять, что он продолжит дело Миндовга — войну с Орденом. Орденский хронист Петр Дусбург пишет о походе Треняты в Пруссию, хотя, казалось, тот должен был заботиться об укреплении своей власти: «Тринота, сын короля литовского, присоединив к себе многих других воинов-язычников, собрал для битвы почти 30 тысяч человек и, приблизившись к земле Прусской, разделил войско свое на три отряда, один из которых он послал на Мазовию, другой — на Помезанию, и обе земли разорил огнем и мечом. Остальные вторглись в землю Кульмскую, и, помимо прочего зла, которые там содеяли, они взяли замок Биргелов, похитив скот и все имущество братьев и тех, кто бежал в упомянутый замок. Братья и прочие люди спаслись, укрывшись в одной башне». Хоть Треняту поддержали Литва и Жемайтия, но все же он не мог считать себя полновластным их правителем. На власть претендовали Тевтивил и Войшелк, и открыто воевать с ними он опасался. Как всегда, пригодилось коварство. Тренята решил расправиться по отдельности с Тевтивилом и Войшелком. Он пригласил Тевтивила к себе делить «добыток Миндовъгов». В Полоцке решили, что пришел час действовать — убить Треняту и присоединить Литву к Полоцкому княжеству. Возможно, на это решение повлияло и желание Войшелка передать Тевтивилу, христианину и брату, «все право свое натуральное в общей Русской вере, если бы он убил Треняту», как считал хронист Матей Стрыйковский. Но намерение Тевтивила выдал боярин Прокопий, и Тренята опередил своего соперника, убил его, а полоцких бояр пленил. Полочане, чтобы освободить своих бояр, вынуждены были принять ставленника Треняты, видимо, князя Герденя. Теперь, когда Полоцк прекратил борьбу, Тренята мог расправиться с Войшелком. Но Войшелк оказался хитрее. Он покинул Новогородок и отправился в Пинск собирать войско. И не без его участия возник заговор против Треняты. По рассказу Ипатьевской летописи, Треняту по дороге в баню убили четыре бывших конюха Миндовга. Но Матей Стрыйковский в исторической книге «О началах» рассказывает иначе: будто бы Войшелк помирился с Тренятой и жил у него при дворе. Сердечная рана мучила его, и Войшелк решил отомстить за смерть отца. Однажды, когда они отправились на охоту, Войшелк напал сзади на Треняту и так ударил мечом по голове, что «аж выбил мозг». После чего убежал в свой монастырь. И все же мы доверимся галицко-волынскому летописцу — современнику тех событий.
Войшелк был безоружен перед своими врагами, и если б не помощь Новогородка и Пинска, то неизвестно, чем бы все закончилось. Как только заговорщики убили Треняту, Войшелк с пинской дружиной пришел в Новогородок, где его ждала уже новогородская дружина. С пинчанами и новогородцами Войшелк пошел в Литву. Летопись представляет этот поход как поход на язычников: «Господи Боже, виждь неправду сию, а прослави имя твое, да не похваляются беззаконии в нечестии своем, и даждь мне помощь и силу изыти на них за имя твое святое, яко прославится имя твое святое».
Войшелка приняли в Литве как законного властителя: «Литва же вся прияша и с радостью, своего господичича», — отмечается в Ипатьевской летописи. Но с «радостью» к Войшелку относились не все. И бывший монах, забыв о христианском милосердии, «поча вороги свое избивати, изби их бесщисленное множество, а друзии разбегошеся, камо кто видя». Это было завоевание Войшелком Литвы и подчинение ее Новогородку, о чем говорит и Новгородская летопись: «Иядъ на поганую Литву и победи я, и стоя на земли ихъ все лето, тогда окаяньным възда Господь под делом их; всю бо землю ихъ оружием поплени». Эта жестокость была вызвана не только политическими соображениями избавиться от противников, привести в послушание недовольных, но и желанием силой уничтожить язычество. Расправившись с внутренними врагами в Литве, Войшелк обеспечил мир с соседями. Он заключил союз с Ливонским орденом, уступил ему Жемайтию. «Всех христиан, которых он нашел пленными в своем государстве, он милостиво отправил назад в Ригу, к магистру. Но затем он дался в обман литовцам, составил с ними заговор и послал в том же году войско в Вик и Пернов и опустошил эти области в сретение Господне (2 февраля). А неделю спустя после этого праздника была дана литовцам битва при Дюнаминде», — сообщает «Хроника Вартберга». Неясно, что послужило причиной прекращения мира с Орденом, может быть, какие-то территориальные споры. Поход в Ливонию закончился поражением, и Войшелк вынужден был искать нового союзника.
Войшелк заключил мир с Галицко-Волынским княжеством, признав себя вассалом владимирского князя Василька Романовича. С его помощью и дрогичинского и луцкого князя Шварна Данииловича Войшелк завоевал балтские земли — Деволтву и Нальшаны. Как в Литве, так и на новых завоеванных землях Войшелк жестоко расправился со своими неприятелями, «ворогы своя избив». Убийца Миндовга Довмонт с дружиной в 300 воинов, боярами, их семьями бежал в Псков, где был посажен на княжеский престол.
Против него Войшелк использовал полоцкого князя Герденя, передав ему Нальшаны. Чтобы выбить Герденя из своей земли, Довмонт-Тимофей (его крестное имя) со своей дружиной и псковичами дважды нападал на Нальшаны. В первом походе он захватил жену Герденя Епраскею с двумя его сыновьями. Летопись XVI века (Воскресенская) называет имена сыновей Герденя — Витень и Андрей. Как известно, Витень станет великим князем литовским, а Андрей — тверским епископом. Во время второго похода Довмонта в 1267 году Гердень погиб, но вернуть Нальшаны у Довмонта не хватило сил. А может, вновь дипломатическую войну выиграл расчетливый Войшелк. Ведь его союз с Орденом угрожал Пскову, и псковичи опасались воевать с Литвой.
На руку Войшелку была и смерть Герденя. Он избавился от сильного удельного князя, а полоцкий посад занял князь Изяслав, который признал его волю. Таким образом, Войшелк объединил под своей властью Новогородскую землю, Литву, Деволтву, Нальшаны и Полоцко-Витебскую землю, чего не смог сделать Миндовг. Союз с Пинским княжеством и покровительство сильного Владимирского княжества гарантировали созданной им федерации стабильность и устойчивость. Так было образовано Великое Княжество Литовское. Его основателем по праву надо считать Войшелка. Первой столицей этого государства был Новогородок.
Немного успел сделать Войшелк на великокняжеском посаде. В 1266 году он вместе с князем Шварном участвовал в походе на Польшу. Объединенное войско опустошило Мазовию и Сандомирское воеводство.
Возможно, инициатором этого похода выступил Войшелк, ибо Шварн оправдался перед польским князем Болеславом: «Не я, но Литва воевала». Целью похода была борьба за ятвяжские земли между Литвой и Мазовией. Видимо, при Войшелке и была присоединена Восточная Судовия, где стал княжить Тройдень, который, вероятно, приходился ему родственником.
Свою державу Войшелк строил по образцу русских княжеств, взяв оттуда не только веру, но и политические, административные и военные структуры власти и методы правления. Войшелк стал для Литвы и «апостолом», и просветителем, и реформатором.
Войшелк крестил Литву в православие. Никоновская летопись сообщает, что он «многих крести, и церкви и монастыри воздвиже». Это же отмечает в «Началах» и Матей Стрыйковский: «Много Литвы язычников к христианству привел... церковь христианскую умножил в Литве».
С целью крестить Литву Войшелк в 1265 году обратился с просьбой в Псков прислать ему священников, но он так и не дождался их и отправился в Полонинский монастырь, чтобы набрать там монахов.
На великокняжеском посаде Войшелк оставил Шварна. Он отговаривал Войшелка от возвращения в монастырь, но тот ответил: «Согрешил есмь много перед Богом и человекы. Ты княжи, а земля ти опасена». Не исключено, что Войшелк, исполнив свой княжеский долг, устроил государство и обезопасил его от врагов, возвратился в монастырь по велению души, ибо решил посвятить себя служению Богу. Случай в истории уникальный — правитель державы добровольно уходит в монастырь, передав власть другому человеку.
Князь Лев Даниилович узнал о приезде Войшелка в Галицию и сообщил об этом дяде Васильке: «Хотел бых снятися с тобою, абы туто и Вошелк был». Василько уговорил Войшелка встретиться с Львом Данииловичем: «Прислал ко мне Лев, а быхом ся сняли. А не бойся ничего же». Войшелку ничего не оставалось, как ехать на встречу с Львом во Владимир. Как рассказывает Ипатьевская летопись, Войшелк, Василько и Лев встретились в доме немца Марколта и «начаша обедати и питии и веселитися». Пьяный Василько отправился спать в монастырь, где остановился Войшелк. Следом сюда приехал Лев Даниилович и предложил Войшелку: «Куме! Напьемся». За хмельной чашей и пробудилась у Льва давняя обида на Войшелка из-за того, что он «дал землю Литовьскую брату его Шварнови». Галицкий князь, возможно, угрозами требовал передачи ему Новогородка. Войшелк не согласился, чем и вызвал гнев у Льва, и тот в пьяном припадке выхватил саблю и зарубил Войшелка.
