Тем временем Рим не переставал считать Литву одним из своих епископств. Церкви Ливонии и Литвы числились храмами сопредельных государств, а папа действовал в Литве через Ливонию. Но приблизительно в то время, когда начал править Гедимин, начался спор между рыцарями и епископом Рижским. Епископ пожаловался папе, что рыцари своей жадностью, тягой к власти и жестоким обращением отвращают народ от христианства. Рыцари заявили, что епископы оказывают влияние на завоеванный народ: настраивают его против рыцарей и поощряют его языческие обычаи. Они доказали папе, что епископ Рижский не раз звал людей действовать против ордена, что епископы вели тайные переговоры с литовскими князьями и распространяли свое влияние на народ, действуя вопреки ордену, и использовали орден только тогда, когда были нужны его услуги. Ввиду таких противоречивых утверждений папа иногда вставал на сторону епископа, а иногда – ордена, не мешая, однако, ни той ни другой стороне продолжать «священный труд» обращения в христианство неверных.
Через епископа Рижского папа получил в 1323 г. сообщение от Гедимина, в котором говорилось, что он готов принять крещение, равно как и весь подвластный ему народ. Он попросил, чтобы рыцарям воспрепятствовали начать войну с Литвой, и заявил, что орден не давал ему установить прямые отношения с курией, что рыцари никак не помогали обращению населения в христиан.
Одновременно были отправлены письма рижским францисканцам и доминиканцам с просьбой прислать в Литву монахов. Письма были также посланы и в Германию с предложением установить свободную торговлю и просьбой прислать колонистов. Папу обрадовало письмо Гедимина, и он приказал ордену прекратить воинственные действия ввиду обращения Литвы в христианство. Архиепископ Рижский заключил дружественный союз с Гедимином, к которому был вынужден присоединиться и орден.
В должное время из Рима прибыли посланники, и, когда подтвердили все договоренности между Литвой и Ливонией, они отправились искать Гедимина, чтобы ввести католическую веру в его столице и других местах. Они намеревались крестить и короновать литовского князя, а затем крестить всех его подданных, но этого они не смогли сделать.
В Вильне стало ясно, что все обстоит совсем не так, как ожидали. Они увидели огромную ненависть к немецкой религии и нашли, к своему удивлению, православные церкви. А также обнаружили, что язычники-литовцы не только угрожают лишить Гедимина власти, если он попытается крестить их, но и истребить всю его семью. Они поняли, что все пруссы и жмудь восстанут, если Гедимин попытается ввести немецкую религию. Кроме того, русские православные подданные Гедимина составляли три четверти всего населения; и от них тоже слышались громкие угрозы. Таким образом, встречая сопротивление с двух сторон, ему было бы очень трудно, если бы он действительно захотел ввести немецкую религию. Гедимин был крещен в православной вере то ли по убеждению, то ли из политических соображений – это мы не можем определить и по сей день, но его мотивы, вероятно, были очень сильными: либо оставаться язычником, либо становиться православным. Он отослал назад папских легатов. Они уехали в гневе и негодовании на правителя-вероотступника. Но Гедимин не считал себя виноватым, виновных он нашел в другом лагере. Каждая сторона обвиняла другую, но было трудно понять, какая из них более вероломна. Неграмотная Литва осуществляла свою внутреннюю переписку на русском языке, но для переписки с Римом и Западом ливонские немцы помогли Гедимину освоить латынь и с этой целью прислали из Вильны монахов. Оказалось, что эти рьяные помощники в своих письмах на латыни, отправленных в Рим через Ригу, писали от имени Гедимина много такого, что он не желал признавать. Во всяком случае, когда из Ватикана грянул гром и по всей Западной Европе его стали называть обманщиком и лжецом, поправшим законы божественные и человеческие, Гедимин оправдывался, говоря, что писцы, писавшие на латыни, неправильно перевели его слова; он никогда не произносил слов, ими написанных.
Немцы теперь стали доставлять больше неприятностей, чем когда-либо. Гедимин оказался втянутым в постоянный конфликт со своими соседями. Рыцари, непрестанно воевавшие на берегах Немана, совершали нападения в форме экспедиций, которые называли «поездками». Со всех уголков Священной Римской империи приезжали толпы людей, чтобы присоединиться к этим экспедициям. В 1336 г. приехали около двухсот рыцарей – графов и князей, и Великий магистр устроил для их развлечения мероприятие, которое можно назвать большой охотой на язычников.