В 1258 году он с помощью Товтивила захватил Новогрудок и захватил княжившего в нем Романа Данииловича. В ответ Даниил Галицкий совершил поход на Новогрудскую землю, взял Волковыск и послал отряды на Гродно и Зельву. Но снова подчинить Новогрудок ему не удалось. Вернув власть над Новогрудком, Войшелк хотел утвердиться и в литовских владениях отца, прежде всего путем распространения там православия. Между отцом и сыном возникла враждебность, которая внешне носила религиозный характер.
В это же время у Миндовга обострились отношения с полоцким князем Товтивилом, со своим двоюродным братом, а также с князем Жемантии, который вступил в сговор с Нальшанским князем Довмонтом, у которого Миндовг отнял жену. Довмонт не рискнул выступить открыто, а ждал удобного момента, чтобы отомстить. Такой момент представился, когда войско Миндовга выступило на Брянщину с целью ее присоединения к Великому княжеству Литовскому. В сентябре 1263 года заговорщики подкупили любимца Миндовга выходца из Рязани Остапа Константиновича, напали на спящего князя и убили его вместе с сыновьями.
В Ипатьевской летописи об этих событиях сказано:
«В лето 6771 (1263). Послал бяшеть Миндовг всю свою силу за Днепр, на Романа на бряньского князя; Довъмонт же бяшеть с ними же пошел на войну, и усмотри время подобьно собе и воротися назад, тако река: „Кобь ми не дасть с вами пойти“; воротивжеся назад и впогна вборзе, изогна Миндовга, ту же и уби его и оба сына его с ним уби Рукля же и Репекья. И тако бысть Миндовгову убитью. По Миндовгови же убитьи, Воишелк убоявъся того же, и бежа до Пиньса и ту живяшеть, а Тренята нача княжити во всей земле Литовьской и в Жемоти…»
В результате гибели Миндовга процесс дальнейшего расширения и укрепления Великого княжества Литовского затормозился. Гибель короля помешала также объединению русских и прибалтийских земель в борьбе против ордена. Как дальновидный политический деятель Миндовог поддерживал союз против крестоносцев. В союз входили князь владимиро-суздальский Александр Невский, князь полоцкий Товтивил, князь витебский Константин – сын Товтивила и жемантийский князь Тренята. После гибели Миндовга союз начал распадаться.
Князь Жемайтии Тренята, утвердившись во всей Литве, решил расправиться с претендентами на Литву – Войшелком и Товтивилом. Товтивил был приглашен к Тряняте в гости и убит. Войшелк укрылся в Пинске. Нальшанский князь Довмонт бежал в Псков и там крестился. Вскоре его посадили на княжение. Через несколько месяцев после убийства Миндовга были убит и Тренята. Войшелк, узнав о безвластии в Литве, решил, что наступил момент брать власть в свои руки и над Литвой, и над Новогрудком. Его поддержали Пинск и Новогрудок. С этой поддержкой он пришел в Литву, где стал великим князем.
Войшелк оказался расчетливым правителем. Поначалу он решил расправиться со своими врагами. Из Ипатьевской летописи: «В лето 6772 (1264). Воишелк же нача княжити во всей земли Литовьской, и поча вороги свое избивати, изби их бесчисленное множество, а друзии розбегошася, камо кто видя…»
Расправившись с внутренними врагами, Войшелк заключил мир с орденом и Галицко-Волынским княжеством. Чтобы получить военную помощь Галицко-Волынского княжества, он признал себя вассалом брата Даниила Галицкого, волынского князя Василька Романовича, а его племянника пригласил помочь в управлении подвластными землями. Вскоре Василько и его племянник прислали свои дружины, с помощью которых Войшелк присоединил к Новогрудку новые земли и стал распространять свое влияние на Полоцкое княжество, которому подчинялся Витебск.
Прошло немного времени и эти белорусские земли соединились в одном государстве – Великом княжестве Литовском, что привело к этническому, а значит и военно-политическому перевесу славянского населения над балтским. В одном государстве Войшелк объединил Литовскую, Нальшанскую, Деволтскую, Новогрудскую, Полоцко-Витебскую и Пинскую земли.