Адначасова заставалася небяспека і з боку аддаленага ўсходняга ворага — Залатой Арды. Пры хане Узбеку ўзнавіліся спробы татар схіліць Літву да ўплаты даніны. З гэтай мэтай у 1315 і 1324 гадах адбыліся татарскія паходы (на жаль, інфармацыя аб іх вельмі скупая). Каб утрымаць хана ад новых набегаў, прыходзілася актывізаваць дыпламатычныя намаганні, слаць паслоў з падарункамі. Гэта каштавала нямала, аднак для Гедыміна характэрным было пры магчымасці вырашаць праблемы не ваеннымі, а дыпламатычнымі сродкамі.
Такі падыход, што можна ацэньваць як прыкмету сталення літоўскага дзяржаўнага кіраўніцтва, пачаў намячацца і ў адносінах да крыжацкай небяспекі. У 1322—1323 гадах вялікі князь накіраваў у Рым некалькі лістоў, дзе выказваў намер прыняць каталіцтва, калі хрышчэнне будуць ажыццяўляць папскія легаты, а не місіянеры Ордэна. Цяжка сказаць, наколькі шчыра выказваўся тут Гедымін. Ён не мог не разумець, што такі крок адразу выбіў бы зброю з рук крыжакоў, але ажыццяўленне яго было звязана з вялікай рызыкай. Непазбежна пачаўся б уплыў каталіцкай царквы на ўнутраныя справы дзяржавы і яе знешнюю палітыку, хрышчэнне ў каталіцызм не магло не выклікаць апазіцыі як сярод прыхільнікаў паганства, так і сярод праваслаўнага насельніцтва дзяржавы.
Здаецца, што сам Гедымін быў не супраць збліжэння з Захадам. Яно адкрывала больш шырокія магчымасці для гандлю, дазваляла прывабліваць кваліфікаваных майстроў, на якіх існаваў вялікі попыт у маладой дзяржаве. Вайна патрабавала кавалёў, збройнікаў, але асаблівая патрэба мелася ў мулярах і дойлідах — у Літве ўпершыню разгортвалася масавае будаўніцтва мураваных умацаванняў. Таму Гедымін у гэты перыяд прыкладае шэраг актыўных дыпламатычных намаганняў. Выкарыстоўваючы старыя зносіны Віценя з рыжскім магістратам, у 1323 годзе дамагаецца нармалізацыі адносін з Лівоніяй: тэрыторыі Ордэна, архібіскупства і Літвы абвяшчаюцца зонай міру і свабоднага гандлю. Адначасова выдае прывілей, у якім запрашае жыхароў нямецкіх вольных гарадоў на льготных умовах перасяляцца ў Літву.
Сталіцай дзяржавы пры Гедыміне становіцца Вільна. Існуе прыгожае паданне пра заснаванне ім гэтага горада пасля вешчага сну, які прысніўся князю ў час палявання. На самой справе археалогія сведчыць, што горад на месцы пазнейшага Крывога замка, на Лысай гары існаваў, прынамсі, з XIII стагоддзя і ўзыходзіў яшчэ ад таго паселішча крывічоў, аб якім гаварылася вышэй. З імем Гедыміна можна ўпэўнена звязваць заснаванне мураванага замка на гары, што зараз носіць яго імя. Такія ж першакласныя па тым часе крэпасці ўзніклі ў Медніках, Крэве, Лідзе, Троках. Тады ж у дзяржаве з'яўляюцца і першыя каталіцкія кляштары: два ў Вільне, адзін у Ноўгародку.
Аднак гэтая бурная рэфарматарская дзейнасць, напэўна, выклікала і моцную негатыўную рэакцыю. Сярод літоўцаў і жамойтаў вера продкаў, запаветы даўніны ўспрымаліся як сцяг барацьбы з агрэсіўным Захадам. Супраць збліжэння з Заходняй Еўропай узнялася свайго роду партыя "непрымірымых". Адначасова гэты курс выклікаў адчайныя супрацьдзеянні Тэўтонскага ордэна, які разгарнуў па ўсёй Еўропе агітацыю, каб не дапусціць пагаднення папы з Гедымінам.
Усё гэта прывяло да таго, што хрышчэнне Літвы ў апошні момант сарвалася. Калі, нарэшце, папскія легаты прыбылі ў Прыбалтыку, ім ветліва растлумачылі, што размовы пра хрышчэнне з'явіліся вынікам непаразумення, недакладнага перакладу Гедымінавых лістоў. Мы можам толькі гадаць, якая ўнутраная барацьба стаяла за гэтым рашэннем Гедыміна даць зваротны ход.
Рэформы не былі цалкам спынены. Захавалася і дзяржаўная верацярпімасць, каталіцкія кляштары працягвалі існаваць. Мір з Лівонскім ордэнам пратрымаўся да 1330 года. Але адначасова працягвалі палаць свяшчэнныя вогнішчы на паганскіх капішчах, у тым ліку і ў даліне Свінтарога ля самых муроў віленскага замка.
Дыпламатычным поспехам Гедыміна спрыяла шматлікасць яго патомства. Ён пакінуў не менш сямі сыноў і столькі ж дачок, што дазваляла замацоўваць міждзяржаўныя пагадненні шлюбамі на любы густ. Сыны набывалі правы на спадчыну тых суседзяў, чый род абрываўся, а дочкі выступалі залогам добрых зносін з зяцямі. Адну з іх ён, як адзначана вышэй, выдаў за Давыда, намесніка гарадзенскага, іншых — за суседніх уладароў. Данміла (у хрышчэнні — Альжбета) стала жонкай мазавецкага князя Вацлава Плоцкага (гэта адбылося ў пачатку панавання Гедыміна). Марыя зімой 1319/20 года ўзяла шлюб з цвярскім князем Дзмітрыем Грозныя Вочы. У 1325 годзе Алдона (Ганна) выйшла за адзінага сына Уладзіслава Лакатка — каралевіча Казіміра. У 1331 годзе Аўгуста абвянчалася з сынам Івана Каліты Сямёнам, а Офка — з сынам Трайдзена Мазавецкага Баляславам. Паводле няпэўных звестак, і апошні ўладар Галіцка-Валынскага княства Юрый Андрэеевіч меў за жонку дачку Гедыміна.