Литовцы представляли реальную угрозу для владений ордена, усугублявшуюся тем, что они зачастую действовали заодно с поляками и русскими, а порою и с татарами, против тевтонских рыцарей в регионе. Литовцы, вопреки своему, более политическому нежели искреннему, обращению в христианство великим князем Миндовгом, по сути своей оставались язычниками. После смерти Миндовга в 1262 г. язычество вновь возродилось, и редкими были те крещеные литовцы, которые остались верными своей новой религии. Литовские племена регулярно грабили соседей и совершали набеги на земли Тевтонского ордена, в ответ на это следовали жесткие репрессии.
В начале XIV в. конфликт между орденом и литовцами усугубился. Кампании, проводимые на литовской территории великим командором Генрихом фон Плотцке с 1311 по 1316 г., позволили ордену сохранить свои позиции. Но приход к власти великого князя литовского Гедимина, родоначальника Ягеллонов, привел к усилению напряжения. В начале 1320 г. Гедимин начал широкое общее наступление на орден; победа, которую он одержал над рыцарями 27 июля при Меденике в Жемайтии, поставила точку на амбициях ордена в этом регионе. Во время сражения магистр ордена Генрих фон Плоцке погиб, как и многие его рыцари. Окрыленные победой, литовцы жестоко расправились с пленными: так, Герхард фон Руден, попавший им в руки, был сожжен живьем вместе с конем во время церемонии жертвоприношения во славу языческих идолов. В многочисленных исторических трудах тевтонские рыцари — и только они — представлены как жестокие воины, уничтожавшие иноверцев огнем и мечом, но справедливости ради следует напомнить, что и противники были не лучше и также жестоко обходились со своими врагами.
После неудачной кампании 1320 г. Тевтонский орден запросил помощи в Германии и Богемии, и тогда был организован очередной крестовый поход. Великий князь Гедимин посчитал разумным вернуться к политике, проводимой его предшественником Миндовгом. Он принял христианство и выдал замуж свою дочь Альдону за сына короля Польши Владислава IV, тогда как тот враждовал с Тевтонским орденом. Своим обращением в христианство литовский князь снимал с себя всякую вину за крестовый поход, направленный против язычников. Война возобновилась в 1322 г. Тевтонские рыцари благодаря подкреплению, полученному из Германии, разорили страну, однако в следующем году языческие племена Жемайтии возобновили свои набеги и захватили Мемель, затем опустошили Мазовию и Добжин, в то время как в Ливонии литовцы напали на Ревель, разрушив и ограбив все церкви и монастыри, которые встретили на своем пути, что ясно доказывало чистую формальность крещения Гедиманаса. В польской Мазовии литовцы разрушили Пулаву, опустошили все земли, сожгли церкви и убили священников и верующих. В 1320-1321 гг. еще далеко было до союзнического договора с Польшей. Но так как поляки не оставили надежды отвоевать Померелию у тевтонских рыцарей, они в 1325 г. возобновили добрые отношения с Гедиминасом.
После состоявшегося брака дочери Гедиманаса с наследным принцем Польши эта союзническая попытка явилась новым этапом сближения между Польшей и Великим княжеством Литовским, к которому стремились и тот и другой, обеспокоенные растущей мощью Тевтонского ордена. Однако в ближайшем будущем о длительном и искреннем союзе между ними, ввиду разрыва между Польшей, глубоко христианской, и Литвой, население которой в своем большинстве оставалось традиционно языческим, говорить не приходилось.
Восточные амбиции Гедимина, направленные на Русь и Черное море, а также постепенное восстановление нормальных отношений между Тевтонским орденом и Польшей вернули видимость мира в отдаленных владениях Тевтонского ордена и Литвы. Тем более что магистр Дитрих фон Альтенбург, который только что получил от императора Людвига V инвеституру на все земли во владении литовцев, одержал над ними победу 15 августа 1338 г. в решающей битве на равнине Даблавкене (Галелукен), недалеко от Мекденика, где восемнадцать лет тому назад были разбиты тевтонские рыцари. Война продолжалась еще некоторое время. Тевтонская армия выдвинулась на литовскую территорию, но не смогла захватить крепость Влиона. Защищая эту позицию, Гедимин погиб в 1341 г. Оба его сына, Ольгерд и Кейстут, поделили между собой наследство, первый из Вильнюса правил Восточной Литвой, в то время как его брат из Каунаса правил Западной Литвой и Жемайтией.