Перелом в Распутине был несомненен. Встретивший его дорогой из Верхотурья односельчанин Подшивалов вспоминает, что «возвращался он тогда домой без шапки, с распущенными волосами и дорогой все время что-то пел и размахивал руками». Другой односельчанин, Распопов, говорит: «На меня в то время Распутин произвел впечатление человека ненормального: стоя в церкви, он дико осматривался по сторонам, очень часто начинал петь неистовым голосом». Такое же впечатление Распутин произвел и на Сенина пятнадцать лет спустя: он «раньше священнослужителей является в храм Божий, встает на клирос и молится. Быстро, быстро и истово крестится и резко взмахивает головой, бьет лбом в землю, лицо и губы его при этом искривляются, зубы оскаливаются, как будто он дразнит кого-то невидимого и хочет укусить, жестикулирует руками и вертит головой во все стороны, оглядывается при поклонах на молящихся и вращает глазами».
Со времени первого паломничества у Григория навсегда остался какой-то надрыв, движения стали порывисты, нервное возбуждение чередовалось с депрессией, речи были отрывисты и бессвязны, порой с заиканием. Он «с трудом подыскивает слова, лицо его при этом передергивается, глаза блуждают и как бы стараются уловить в воздухе ту фразу, которая выразила бы его мысль», — пишет Сенин. «Ни одной фразы он никогда не произносил ясной и понятной. Всегда отсутствовали либо подлежащее, либо сказуемое, либо и то, и другое. Поэтому точно передать его речь абсолютно невозможно, а записанная дословно она не может быть понята», — вспоминает князь В.Н.Шаховской, знавший Распутина последние годы его жизни.
Что бы ни было последней причиной или причинами для Григория начать новую жизнь, почва для этого готовилась постепенно: с юности задумывался он иногда над вопросами «вечными», над вопросом смысла жизни, не умея достаточно ясно сформулировать и понять, что мучает его. «Пахал усердно, — пишет он, — но мало спал, а все ж таки в сердце помышлял, как бы чего найти, как люди спасаются». В двенадцати верстах от Верхотурья, в Пермских лесах, жил схимник старец Макарий, у которого Григорий провел большую часть своего трехмесячного паломничества и которого всю жизнь считал своим учителем. Здесь, по приказу старца, изнурял он свое тело долгими молитвами и постом, чтобы закалить неокрепший дух. Он рассказал Макарию о своем видении, и тот, сказав, что Бог избрал его для великих дел, отправил Григория с паломничеством в Святую землю.
Побывав еще у двух северных схимников — Ильи Валаамского и Адриана Кыртымского, Распутин со своим другом Михаилом Печеркиным отправился в Афон, а оттуда в Иерусалим. Большую часть пути прошли они пешком, Печеркин остался в Иерусалиме, а Распутин вернулся в Россию — и всю ее исходил за десятилетие. Был в Киеве, Троице-Сергиеве, на Соловках, в Валааме, Сарове, Почаеве, в Оптиной Пустыни, в Нилове, Святых Горах, во всех местах, сколько-нибудь знаменитых своей святостью.
«Много путешествовал и вешал, т. е. проверял все жизни, — пишет Григорий, — паломничеством мне пришлось переносить нередко всякие беды и напасти, так приходилось, что убийства предпринимали против меня… и не один раз нападали волки, они разбегались, и не один раз нападали хищники, хотели похитить и обобрать, я им сказал, что не мое, а все Божие, вы возьмите у меня — я вам помощник, с радостию отдаю. Им что-то особенно скажет в сердцах ихних, они подумают и скажут: откуда ты и что такое с тобой? Я сей человек, посланный, брат вам и преданный Богу. Теперь это сладко описать, а на деле-то пришлось пережить». Он, однако, вынес отрицательное впечатление о монастырской жизни, найдя в ней много лицемерия, смутило его, в частности, сожительство монахов с женщинами. Поделился он сомнениями со старцем Макарием, и тот якобы сказал: «Не удалось спасти душу в монастыре — спасай в миру».
Обычно летом Григорий возвращался в Покровское, «по-прежнему жал, косил наравне с женой и стариком-отцом, а как только кончалось время полевых работ, он брал палку, одевался странником и уходил в монастырь». Только один раз исчез он из дому на целых два года, по-видимому, в 1901–1903 годах. Возвращения его были праздником для жены и детей, дети особенно любили слушать его рассказы о путешествиях, о святых старцах. Но он предавался с детьми и простым забавам: играл с ними в мяч, катал на тележке и учил сына, как обращаться с лошадьми.
В своем дворе Распутин вырыл яму, где устроил молельню — «вдруг проникла во мне, — пишет он, — …что вот сам Господь не избрал царские чертоги, а выбрал себя ясли убогие… Мне, недостойному, пришло в голову достигнуть, взял выкопал в конюшне — вроде могилы — пещерку, вот я там уходил между обеднями и заутренями молился… Так продолжалось лет восемь».