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