Борьба с Тевтонским орденом была трудной не только потому, что Орден обладал сильной военной организацией, ориентированной на постоянное ведение войны. С начала XIV в. к Ордену присоединилось рыцарство из многих европейских католических стран, чтобы принять участие в походах против язычников. Положение несколько облегчали раздоры в лагере противника. В 1297 г. началась война между Орденом и Ригой, и рижане стали искать помощи у литовского великого князя Витеня. Дружественные связи с Ригой стремился поддерживать и Гедимин. В борьбе с Орденом Литва стремилась прорвать кольцо окружавших её католических государств и установить хотя бы с некоторыми из них мирные отношения. Во второй половине XIII в. литовским правителям удалось заключить союз с Болеславом II Мазовецким (эти соглашения были скреплены брачными связями). Политику предшественников продолжил Гедимин, который в начале 1320 гг. выдал дочь, получившую в крещении имя Елизавета, за сына Болеслава II князя Вацлава Полоцкого. Однако этот союз мало что давал Литве. Мазовецкие князья были слишком слабыми, чтобы помогать Литве в борьбе против Ордена, наоборот, из-за них литовские правители оказывались вовлечёнными в споры мазовецких князей с польскими соседями. Гораздо большего успеха Гедимин добился, когда ему удалось заключить соглашение о союзе с Владиславом I Локетком. Польский король находился в конфликте с Орденом, захватившим в начале XIV в. польское Поморье, и нуждался в союзниках для борьбы с крестоносцами. Союз двух государств скрепил 16 сентября 1325 г. брак наследника Владислава I Локетка будущего польского короля Казимира III Великого (1333–1370 гг.) и дочери Гедимина, получившей в крещении имя Анна. В 1326 г. отряд из 1200 всадников во главе с наместником Гродно князем Давидом участвовал в походе Владислава I Локетка против одного из его противников – маркграфа Людовика Бранденбургского. Войска союзников дошли до Франкфурта-на-Одере. Во многих странах латинской Европы это дало основание для резких обвинений польского короля в том, что он воюет против христиан в союзе с язычниками. Это событие не привело в то время к разрыву польско-литовского союза, но когда в 1330 г. Владислав I Локетек, вступив в войну с Орденом, призвал на помощь союзников, то венгры отказались вести войну вместе с язычниками, Гедимин был вынужден увести войска. На этом польско-литовское сотрудничество надолго прервалось. К православию Гедимин и княжеская семья в целом относились терпимо. Судя по именам, христианами были братья Гедимина – Воин, сидевший в Полоцке, и Фёдор, упомянутый в записях, сделанных в канцелярии митрополита Феогноста. Православными были и сыновья Гедимина, сидевшие на белорусских землях: князь Наримант (Глеб) в Полоцке, а затем в Пинске и Кориат (Михаил) в Новгородке (современный город Новогрудок, Белоруссия); сыновья, наделённые отцом землями на собственно литовской территории (к их числу принадлежал и Ольгерд, лишь позднее ставший князем в Витебске), оставались язычниками. Гедимин стремился создать для православных в своих владениях особую церковную организацию, отделённую от Киевской митрополии. Такая особая Литовская митрополия была учреждена императором Андроником II Палеологом (1282–1328 гг.) и патриархом Иоанном XIII Гликой (1315–1319 гг.).