После того как Орден меченосцев в 1237 г. был поглощен Тевтонским орденом и переименован в Ливонский орден, племенные сообщества юга Земгале по понятным причинам почувствовали еще большую угрозу. Литовские земли, непосредственно примыкавшие к Земгале, — Жемайтия и Аукштайтия — отреагировали на эту новость продолжением набегов далеко в пределы территорий, контролируемых теперь Ливонским орденом; с другой стороны, два ордена — Тевтонский к западу от литовских земель и его ливонское подразделение на севере склонялись к тому, чтобы считать эти и другие территории, расположенные еще дальше на юг, такими же языческими землями, как и те, что они уже завоевали.

Однако в действительности литовские земли оказались куда более трудной добычей для крестоносцев. Туда было гораздо сложнее отправиться с войском, поскольку там было меньше равнин, но больше болот и лесов. Литовцы четко обозначили, что они с большей вероятностью, чем их северные соседи, могут организовать жесткое и последовательное сопротивление внешним вторжениям. Такое сопротивление было результатом развития, которого не знали северные племена, то есть формирования государства, населенного и управляемого литовцами. Здесь подчинить и христианизировать местных политических лидеров и поддерживающую их элиту было гораздо более проблематично.

Становление государства — длительный процесс, и хроники, описывающие события XII и XIII вв., не предлагают точной информации, как это происходило на литовских землях. Стартовая точка была той же, что и на севере: здесь существовали взаимно антагонистичные племенные сообщества, возглавляемые политическими лидерами, способными время от времени организовать военные операции друг против друга и уязвимых соседей. Не вполне ясно, сколько именно было подобных объединений; помимо наиболее крупных обозначаемых в источниках регионов, Жемайтии и Аукштайтии, в их пределах и за ними существовали меньшие объединения. В 1219 г. договор в Волынью — землей, примыкавшей к Литве с юга — был удостоверен двадцатью одной подписью литовских князей. Историки позже назвали их «главнейшими литовскими князьями» и никто из них в договоре не был обозначен как главный по отношению к остальным. По существующим свидетельствам, наиболее успешная попытка объединить территории, контролировавшиеся этими лидерами, в нечто напоминающее государство была предпринята аукштайтским вождем по имени Миндовг (1253–1263), который сыграл в этом регионе роль объединителя, исполненную в Англии королем Альфредом Великим тремя столетиями ранее. Считается, что усилия Миндовга принесли плоды в третье и четвертое десятилетия XIII в., когда меченосцы закончили покорение эстов на севере и начали решать проблемы с куршами и земгалами.

Методы, которыми Миндовг осуществлял это объединение, порой были жестокими: убийства и изгнание соперников, вторжения на земли менее значительных вождей и превращение их в своих вассалов. Также он значительно преуспел в организации династических браков родственников с потенциальными соперниками, создав таким образом сеть лидеров, связанных с ним как узами родства, так и договоренностями о верности. К 1245 г. Миндовг был провозглашен «Великим» и «верховным вождем» литовцев; в 1251 г., без всякого завоевания его земель крестоносцами и невзирая на то, что ранее сам он сопротивлялся христианизации, он принял христианство и был крещен; и в 1253 г. Миндовг принял литовскую корону с благословения самого папы Иннокентия IV. Очевидно, по расчетам Миндовга, христианизация была одним из способов уберечься от угроз Ливонского ордена и, возможно, способом прекращения рейдов Тевтонского ордена с запада. Принятие христианства дало ему возможность и время провести комплекс мер, связанных с построением государства: создать собственный двор, бюрократический аппарат центральной администрации, организовать систему воинской повинности и даже ввести общую валюту. Однако на этом пути были и потери. В обмен на то, чтобы считаться «христианским королем», Миндовг был вынужден уступить контроль над Жемайтией (северо-западной частью литовских земель) Ливонскому ордену и церкви. Его жесткие методы объединения озлобили других известных литовских лидеров (и их семьи), полагавших, что они имеют столько же прав на главенство, сколько и Миндовг. Соответственно, их лояльность была в лучшем случае временной. Русские княжества на востоке особенно не одобряли принятия Миндовгом христианства от римского понтифика, а не от константинопольского патриарха. Помимо этого, сомнительно, что обращение в христианство Миндовга и его двора сколько-нибудь значительно сказалось на основной массе населения Литвы; очевидно, смена веры в данном случае являлась больше политическим, чем духовным актом. Осознавая, насколько папство заинтересовано в новообращенном христианине такого статуса, Миндовг провел несколько лет, играя с папой в кошки-мышки, то обещая обратиться, то передумывая, а тем временем папа был вынужден откладывать провозглашение против него крестового похода.

В любом случае карьера Миндовга как христианского правителя продлилась лишь около десяти лет — и все из-за жемайтов. Они не вполне приняли тот факт, что Миндовг своевольно «передал» их во власть ордена и церкви; продолжая бороться с орденом, в конце концов они вновь обратились к Миндовгу за помощью. Он прислушался к жемайтам, вновь вспомнив о своем прежнем статусе противника христианизации или, по меньшей мере, о тех ее методах, которые практиковал орден. Однако коалиция, которую он помог сформировать против Тевтонского ордена и его ливонской ветви, не имела военных успехов. Миндовг был убит в 1263 г., очевидно, обиженными литовскими вождями. Остается открытым вопрос, стал ли он отступником в последние годы жизни, и поэтому папы продолжают ссылаться на Миндовга как на «христианского короля». Однако государство, которое он основал, продолжало существовать даже несмотря на то, что непосредственно после смерти правителя возникли проблемы с наследованием. Тройнат, предводитель жемайтов, на короткий период наследовал Миндовгу как верховный вождь; затем его сменил сын Миндовга Войшелк, который через некоторое время обратился в православие. Цепь менее значимых лидеров, наследовавших Миндовгу, невозможно проследить точно за отсутствием адекватной информации в источниках, но очевидно, что наследство Миндовга не включало важнейшего элемента, способного укрепить Литовское государство, а именно стабильной династии. Существование Литовского государства как жизнеспособного образования на протяжении нескольких десятилетий после смерти Миндовга кажется чудом, учитывая множество претендентов на его титул из других знатных семей и внешние угрозы, которые никуда не исчезли. Однако к началу XIV в. политическая ситуация стабилизировалась, поскольку притязания на трон были высказаны семьей, которая стала впоследствии династией Гедиминовичей. Как именно Гедиминовичи смогли отстоять свои права, сегодня точно неизвестно: Гедимин (ум. 1341), давший свое имя династии и правивший с 1316 по 1341 г., был третьим среди правителей из этой семьи. В определенном смысле он стал истинным преемником Миндовга благодаря своему таланту правителя.

Одним из поводов для беспокойства для первых Гедиминовичей был Тевтонский орден, постоянно демонстрировавший экспансионистские устремления в восточном направлении. До того как этот орден крестоносцев появился на южном побережье Балтики в конце 20-х годов XIII в. по приглашению мазовецкого князя и создал там свой плацдарм, он некоторое время функционировал на Святой земле. Основные цели ордена заключались в том, чтобы создать собственное государство, а также христианизировать пруссов-язычников, окружавших территории ордена; и ко второй половине XIII в. обе эти цели были близки к осуществлению. Когда в состав ордена вошел Ливонский орден (бывший Орден меченосцев, в 1260 г.), у тевтонцев появились необходимые для достижения этих целей ресурсы. Пока Ливонское ответвление ордена продолжало борьбу с язычниками на восточном побережье, основные силы Тевтонского ордена стремились к тому, чтобы расширить границы своего государства на восток, в литовские земли, и испытали на этом пути как победы, так и поражения. Однако с ростом сил Литовского государства перспективы ордена относительно расширения на восток становились все менее реальными; литовцы успешно блокировали попытки такого расширения, так же как и попытки ливонцев продвигаться на юг. В то же время растущая мощь государства Тевтонского ордена и его политика, направленная на расширение внешних границ, блокировали любые попытки продвижения на север польских князей (в том числе мазовецких), стремившихся к максимальному приближению границ своих владений к южным берегам Балтийского моря.