Гедимину также угрожал отдаленный восточный враг—Золотая Орда. При хане Узбеке возобновились попытки татар склонить Литовское княжество к уплате дани. С этой целью в 1315 и 1324 годах были предприняты татарские походы на Литву.
Чтобы удержать золотоордынских ханов от новых набегов Гедимин активизировал дипломатические усилия и часто слал послов с богатыми подарками в Сарай-Бату. Это дорого стоило казне, но Гедимину было свойственно решать по возможности проблемы не военными, а дипломатическими средствами.
С целью предотвратить новые набеги крестоносцев Гедимин отправил в Рим несколько писем, в которых высказал намерение принять католичество, но лишь в том случае, если крещение будут осуществлять папские легаты, а не миссионеры Тевтонского Ордена.
Безусловно, этот шаг лишил бы действия крестоносцев их пропагандистской основы, но его осуществление было связано с большим риском. Неизбежно усилилось бы влияние римской курии на внутренние дела Великого княжества Литовского и его внешнюю политику. Крещение в католицизм не могли не вызвать оппозицию как среди сторонников язычества, так и среди православного населения государства.
Но сам великий князь всегда стремился к максимальному сближению с Западной Европой. Это открывало Литве более широкие возможности для отечественной торговли, позволяло привлекать квалифицированных мастеров, в которых молодое государство ощущало сильную потребность.
Непрерывные войны, которые была вынуждена вести Литва, требовали постоянного притока кузнецов и оруженосцев, но наибольшая нужда ощущалась в строителях — при Гедимине впервые разворачивалось массовое строительство каменных укреплений.
Используя старые связи князя Витеня с рижским магистратом, Гедимин добивается в 1323 году нормализации отношений с Ливонией. Была принята совместная декларация, которая объявляла территории Пруссии, Ливонского архиепископства и Литовского княжества зоной мира и свободной торговли. Одновременно Гедимин издал привилей, в котором приглашал жителей немецких вольных городов переселяться в Литву на льготных условиях.
Столицу Великого княжества Литовского Гедимин перенес в Вильно (современный Вильнюс). Существует красивая легенда про основание великим князем этого города после вещего сна, который приснился ему после охоты. На самом же деле археологи полагают, что город на месте позднейшего Кривого замка на Лысой горе уже существовал с XIII века. Город был основан на месте поселения древних кривичей.
С именем Гедимина связано основание каменного замка на горе, которая сейчас носит его имя. Такие же первоклассные по тем временам крепости возникли в Медниках, Креве, Лиде и Тракае. Тогда же в Великом княжестве Литовском появляются и первые католические костелы — два в Вильно и один в Новоградке.
Однако бурная реформаторская деятельность Гедимина вызвала сильную негативную реакцию части населения страны. Среди литовцев и жемойтов вера предков и заветы старины воспринимались как символ борьбы с агрессивными крестоносцами. Против сближения с Западной Европой выступила партия «непримиримых», вокруг которых сплотилась вся оппозиция княжества.
Одновременно курс Гедимина на сближение с Западом вызвал отчаянное противодействие Тевтонского ордена. Крестоносцы развернули через своих представителей по всей Европе агитацию против соглашения папы римского с Гедимином. Все это привело к тому, что крещение Литвы сорвалось в последний момент.
Когда папские легаты прибыли в Вильно, им сказали, что беседы о крещении Литвы объясняются недоразумением, некачественным переводом писем великого князя. Гедимин вынужден был отказаться от намерения крестить Литву под сильным давлением оппозиции.
Однако реформы Гедимина не были окончательно свернуты. Государственная веротерпимость, возведенная в ранг закона, сохранялась. Продолжали существовать и действовать католические костелы. Но одновременно в долине Свинтарога, у самых стен виленского замка, пылали по ночам священные огни на языческих капищах. Мир с Ливонским орденом продержался до 1330 года.
Дипломатическим успехом Гедимина способствовала многочисленность его потомков. У него родилось семь сыновей и семь дочерей, что позволяло укреплять международные соглашения браками на любой вкус. Сыновья Гедимина имели право наследовать престолы тех княжеств, династии которых обрывались, а дочери выступали залогом добрососедских отношений с зятьями.
Одна дочь Гедимина стала женой Давыда — лучшего литовского полководца. Другая — Данмила, в крещении Альжбета, вышла замуж за мазовецкого князя Вацлава Плоцкого. Третья дочь Мария в 1320 году вышла замуж за тверского князя Дмитрия Грозные Очи. Четвертая дочь Алдона, в крещении Анна, вышла замуж в 1325 году за единственного сына польского короля Владислава Локетека — королевича Казимира. Пятая дочь Августа в 1331 году обвенчалась с сыном великого князя московского Ивана Калиты Семеном. Шестая дочь Офка — с сыном Трайдена Мазовецкого Болеславом. Седьмая дочь Гедимина вышла замуж за последнего правителя Галицко-Волынского княжества Юрия Андреевича.