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