Так, по благословению игумена Иадора, инок Алексий стал паломником во Святую Землю, и в самый день главного праздника, в Светлое Христово Воскресенье, утром, отправился в неблизкий путь. Пятеро братьев обители вместе с настоятелем проводили его до ворот монастыря, с каждым он расцеловался и шагнул за ворота в новую для себя жизнь — пешую.
Снег Страстной пятницы продержался только до Пасхи, и теперь уже было сухо, почти не грязно на дорогах. Ходко шел Алексий всю Светлую седмицу и в пятницу пришел в град Москву, основанную прадедом Александра, князем Юрием Владимировичем, прозванным Долгоруким. Тут Алексий ночевал в монастыре Святого Георгия, который в тот же день посетил главный московский воевода Филипп Нянька и сказывал, что в татарах объявился новый великий вождь по имени Батый, алчущий новых завоеваний в Русской земле.
От Москвы дни странника полетели всё быстрее и быстрее, потому что он уже стал привыкать к своей пешеходной жизни, и ноги поутру уже сами в путь просились. Еще через пять дней он ночевал в Калуге, праздник Вознесения справлял в Чернигове, здесь прожил несколько дней в монастыре Михаила Архангела, недавно основанном, помогал братии в строительстве, а в самый последний день там же имел беседу с посетившим монастырь князем черниговским Михаилом Всеволодовичем. Тот выслушал его рассказ про птичье знамение и сон Иадора с волнением и сказал, что и ему был вещий сон — мол, придет зверь Атый, через которого он, Михаил, жизни лишится, но обретет небесную обитель. Денег давал князь Алексию, но паломник взял ровно столько, чтобы не совсем с пустой мошной дальше двигаться.
В конце июня он пришел в Киев и почти целую седмицу прожил в Печерской лавре, незаметный среди многочисленной братии. Затворялся в пещерах, молясь Богу об успешном своем паломничестве и об Александре. Видел однажды самого митрополита Иосифа. Общался больше всего с диаконом Мартирием и монахом Авраамием, беседовал со старцами Пергием и Меладием, которые тоже говорили о грядущем звере, только Пергий назвал его Атуем, а Меладий — Батыем.
Отпостившись с печерскими монахами до Петрова дня, Алексий отправился дальше и почти месяц брел до Галича, куда притек как раз в день памяти убиения Бориса и Глеба. Тут случилось с ним недоразумение, чуть было не стоившее ему свободы, а то и жизни. Соблазнился он плыть на ладье вниз по Днестру с латинскими проповедниками. Уж очень приятно казалось ему поплавать по речке, к тому же и жара стояла несносная, а под парусом — тень, прохлада. Но на второй день плавания он узнал, с какой целью плывут в половецкую землю латины. Оказывается, с недавних пор римский папа образовал там Куманскую епархию, возглавляемую епископом Теодориком, и сии новые миссионеры направлялись в устье Днестра учреждать католические приходы. В общем, Алексий вскоре с ними разругался, да так, что они ссадили его на берег и оставили одного среди диких мест у подножия Подольской возвышенности. И дальше долго шагал он по бездорожью и безлюдью, несколько раз едва не нарвался на половецкие разъезды и чудом не попал к степнякам в плен или под нож, одною молитвою огражден бысть.
Умирая от голода, Алексий добрался до валахов и тут двадцать дней трудился у одного скотовода, чтобы заработать себе на пропитание и новую обувь. Лишь после Успения Богородицы отправился он далее, пересек Дунай, взошел на горы Балканские, побывал в столице Болгарского государства, в древних монастырях, где всюду его привечали и хорошо угощали, из каждого уходил он с запасом еды и красного вкусного вина. Болгары, недавно объединившиеся с никейцами против латинян, очень полюбились ему веселым нравом и христолюбием. Приближалась осень, дни становились нежаркими, идти было все легче и легче — самое время для пешехода, когда жара спадает, а холода еще не взяли власть. К празднику Воздвижения Честного и Животворящего Креста Господня инок Алексий радостно приближался к Константинополю и в виду Царьграда пел свой любимый крестовоздвиженский тропарь, вставляя в него моление о победах Александра:
— Спаси Господи люди Твоя и благослови достояние Твое, победы благоверному князю Александру Ярославичу на сопротивные даруя и Твое сохраняя крестом Твоим жительство.