Около 1254 года Даниил принял королевскую корону и скипетр от папы, короновавшись в Дорогочине. Поэтому Миндовг вынужден был вернуть ему Чёрную Русь в качестве лена. Несмотря на то что папа римский «позволил» литвинам нападать на Волынь, Миндовг остался верен союзу с Даниилом, по крайней мере, до нападения на Литву татар в 1258 году, в котором по их требованию участвовали и галицко-волынские войска. В начале 60-х годов XIII века Миндовг, скорее всего, уже восстановил свою власть над Чёрной Русью, не смотря на то что к тому времени опять вернулся в язычество и формально потерял право быть христианским королем. Кстати, вплоть до последних лет правления Витовта становиться таковыми великие литовские князья особо и не стремились.

Насчет столицы Миндовга и места его коронации ведутся споры, но наиболее вероятно, что это был Новогродок. Во всяком случае, после этого именно Новогродок еще 70 лет оставался столицей формирующегося Литовско-Русского государства. Даже после переноса князем Гедимином в 1323 году столицы государства в Вильно (Вильню), а своей резиденции в Трокай (Троки), замки Чёрной Руси — Гродненский, Лидский, Новогродский — сохраняли статус великокняжеских владений вплоть до конца существования ВКЛ. К примеру, на рубеже XV века князь Витовт держал свой двор в «Старом замке» Гродно, а Лидский замок обычно использовался для проживания (заточения) почетных гостей и высокопоставленных пленников великого князя Литовского.

Лидский замок начала XIV века до реконструкции.

Созданное Миндовгом государство, однако, было непрочным. Хотя он и провозгласил себя властителем литовских племен, кроме него хватало других князей, действующих если не самостоятельно, то вполне свободно. Они продолжали совершать набеги на пограничные земли Руси, Ливонии, Польши и Тевтонского ордена. А сам Миндовг в 1262 году мстил князю Васильку за его участие в татарском походе под предводительством тёмника Бурундая, напав на волынские города. Набег был неудачным, и обратно литовские отряды отступают через Пинскую землю, что еще раз свидетельствует в пользу нахождения «Литвы Миндовга» между Пинским и Новогродским княжествами.

На этом более-менее достоверные сведения о первом объединителе Литвы теряются. Разные источники датируют смерть Миндовга между 1263–1264 годами, но, похоже, он был убит в 1263 году в результате заговора подвластных ему князей, недовольных политикой централизации. Таким образом, первый великий князь Литовский пал жертвой своей политики, лишь начав создание государства. Однако он создал крепкий плацдарм, на базе которого в дальнейшем и было построено ВКЛ.

После длительной междоусобной борьбы в 1264 году великим князем Литовским становится сын Миндовга Войшелк, который еще во время его княжения был посажен отцом на княжение в Новогродке. Вскоре Войшелк крестился в православие и выразил желание принять монашеский постриг, отказавшись от княжеских прав. Но когда он узнал о смерти отца, то покинул монастырь, собрал в Новогродке и Пинске достаточно сильное войско, после чего жестоко расправился с заговорщиками. Было истреблено множество людей, а триста семейств литовских в поиске убежища выехали в Псков. Войшелк ненадолго становится правителем Литвы, так как, придя к власти, вновь от нее отрекается и передает княжение своему шурину Шварну, а сам опять уходит в монастырь. Таким образом, присоединение Литовского княжества к Галицкому становится весьма реальным. Но этому помешала зависть к брату старшего сына Даниила Льва. Обманом он убивает Войшелка и ненадолго становится правителем Литвы, но уже спустя полгода-год великим литовским князем избирают Тройденя, который правил в 1270–1282 годах. Судя по имени, он тоже был славянином. Во всяком случае, его братья Борза, Сурьпутия, Лесия и Свелкения, как утверждает Ипатьевская летопись, были православными.

В общем и целом Тройдень продолжил политику Миндовга, но более вяло, избегая набегов вглубь русских земель и ограничиваясь завоеваниями небольших приграничных городов. Более успешной была его борьба с тевтонской агрессией — в 1278 году Тройдень разбил войско Ливонского ордена. Тем не менее при нем Великое княжество Литовское состояло из тех же земель, что и при Миндовге: Аушкайтии и части Жемайтии (Жмуди) в современной Литве, Чёрной Руси с городами Новогродок (столица Литвы), Гродно, Волковыск, Слоним и небольшой северо-западной части Полоцкой земли с городом Браслав (Бряславль).

В 1283 году великим литовским князем становится Домонт, но в 1265 году он, как отмечает Лаврентьевская летопись, погиб в битве с объединенными силами своих противников, поддержанных тверским князем. Кто правил Литвой в 1285–1293 годах, доподлинно неизвестно, поэтому многие авторы помещают в этом времени не только выдуманных персонажей, но и выдуманные события. Бесспорным является лишь то, что политический центр Великого княжества Литовского составляло тогда Новогродское княжество Чёрной Руси и часть уже значительно славянизированной Литвы. Есть основания полагать, что и Гедиминовичи из Трокского княжества, скорее всего, тоже были славянами. Во всяком случае, на всех доступных картах это княжество входит в ареал расселения славян.

Формирование государства при первых Гедиминовичах проходило очень динамично, причем именно славянские земли становились в то время опорой великого князя Литовского в его борьбе с непокорными племенными княжениями собственно литовцев. Способы присоединения новых земель были различными. Многие русские земли добровольно вошли в состав Литовской Руси. Наряду с этим некоторые территории (например, Смоленск) на протяжении десятилетий приходилось покорять силой оружия, хотя с присоединением к ВКЛ новых русских земель власть на местах практически не менялась: новых порядков старались никому не навязывать. Кроме того, новое государство давало литовцам и литвинам защиту от немцев, а русским людям — прибежище от татар. Первые и самые ранние победы над монголо-татарами, например, были одержаны русскими ратями в союзе с литвинами и этническими балтами.

После смерти Тройденя и преодоления очередного периода междоусобиц в 1293 году власть в Великом княжестве Литовском силой захватил трокайский князь Витень, правивший до 1316 года. Опираясь на Новогродское, Гродненское и отчасти Полоцкое княжества, он вновь возрождает сильное государство, достаточно быстро распространив свою власть на все литовские земли. Одновременно Витень возобновляет войну с Тевтонским и Ливонским орденами, которые тогда резко усилили свой натиск на литовско-русские земли, поощряемые Римской католической курией и западноевропейскими феодалами, а также потому, что в период смут и борьбы за власть в ВКЛ должного отпора от литвинов не получали. Тевтонцы, в частности, приступили к активному строительству своих замков и крепостей не только на границе с Литвой, но и на ее территории. Ответным шагом великих литовских князей стало массовое строительство замков на границах с Тевтонским орденом и в ближайшей глубине от них, в основном по течению Немана.