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