После побега террорист скрывался в Турции в течение нескольких месяцев, затем нелегально перешёл турецко-иранскую границу, а уже из Ирана выехал в ФРГ. Он был снабжен паспортом на имя индийского гражданина Йогиндера Сингха, еще одним фальшивым паспортом, выданным службой безопасности и управлением вилайета в городе Невшехире (Анатолия) на имя турецкого гражданина Фарука Озгуна. В этом документе все подлинное — печати, подписи, сам бланк, украденный из тиража в национальной типографии, лишь вместо фотографии Озгуна было вклеено фото Агджи. Реальный Ф. Озгун был впоследствии арестован как соучастник, так же как и бывший глава полиции Невшехира, поставивший свою подпись на фальшивом документе 11 августа 1980 г. Еще один паспорт, который получил впоследствии Агджа, на имя ливанского гражданина Али Хуссейна был выкраден из официальных инстанций в Ливане. Внушительная коллекция фальшивых документов Агджи пополнилась впоследствии западно-германским паспортом, выданным в ФРГ полицейским комиссаром В. Удо за соответствующую мзду в 15 тыс. марок.
В ФРГ у Агджи оказалось много влиятельных «друзей», особенно во Франкфурте-на-Майне, где и сегодня на Гутлейштрассе 173 размещается штаб-квартира «серых волков» в Западной Европе. Их предводитель — Муса Сердар Челеби, заправила крупной международной сети контрабандной торговли оружием и наркотиками, имел и собственную сеть убийц для усмирения непокорных. Горный инженер по образованию, зарегистрированный в ФРГ в качестве торговца, Челеби являлся председателем федерации так называемых демократических обществ идеалистов из числа турок эмигрантов, собственником газеты «Йени хадеф» («Новая цель») на турецком языке. За этим почтенным фасадом скрывалась нелегальная организация.
Челеби помог Агдже обосноваться в ФРГ. При его поддержке террорист не чувствует себя стесненным в средствах, живет на широкую ногу, учит немецкий язык и даже сочетается браком с немкой Кристиной Кляйн, связанной с террористическими группировками. Фальшивые паспорта ему не помеха.
Позже в римском суде Агджа почему-то отрицал очевидное, заявляя, что не был ни во Франкфурте-на-Майне, ни в ФРГ. Правительство ФРГ объявило, что оно «решительно отвергает обвинения Турции в отношении западногерманских властей в связи с покушением на папу Иоанна Павла II». На пресс-конференции в Бонне 20 мая 1981 г. представитель правительства Лотар Рюэль заявил, что «не имеется никаких сведений о пребывании в ФРГ, даже временном, Мехмеда Али Агджи».
Такое заявление довольно странно. Компетентные органы ФРГ всегда располагали полной информацией об Агдже, но на обращения Интерпола и Турции не реагировали. Западногерманский корреспондент турецкой газеты «Миллиет» Орсан Имен отмечал в интервью советской «Литературной газете» в июле 1983 г.: «Наше посольство в ФРГ четырежды предостерегало боннские власти вербальными нотами о замеченном турками появлении Агджи в различных пунктах от Франкфурта-на-Майне до Мюнхена». В ноябре 1980 г. выходящий в ФРГ журнал «Тюркай-информационен» писал, что «разыскиваемый террорист Агджа находится в ФРГ», после чего все турецкие газеты, которые можно было купить в каждом западногерманском киоске, опубликовали на первых полосах фотографию Агджи. Объединенная федерация турецких трудящихся в ФРГ (ФИДЕФ) потребовала тогда, чтобы министр внутренних дел издал приказ об аресте Агджи, но, как известно, все эти акции не вызвали никаких ответных мер со стороны западногерманских властей.