Односельчане рано заметили за Распутиным стремление взять, что плохо лежит. Один из них показывал, что однажды он поймал Григория на мелкой краже и «ударил его колом настолько сильно, что у него из носа и рта ручьем потекла кровь, и он, потеряв сознание, упал на землю». Его близких друзей-конокрадов (по-нынешнему – автоугонщиков) выслали по приговору сельского схода, однако к нему самому эту меру не применили из-за недостатка улик. Замечу, что до уголовного суда дела о конокрадстве, как правило, не доходили. Крестьяне, для которых потеря лошади часто означала разорение и угрозу голодной смерти, с конокрадами расправлялись жестоко и своим судом, нередко калечили их и даже убивали.

Отец увлечение сына религией не оценил, видя в этом лишь предлог, чтобы отлынивать от работы. Распутин дома все больше чувствовал себя чужим и пустился в странствования.

В 1893 году Распутин странствовал по святым местам России, побывал на горе Афон в Греции, потом в Иерусалиме. Он встречался и завязывал контакты со многими представителями духовенства, монахами, странниками. У Григория Ефимовича проявились хорошие гипнотические способности. Он считался хорошим целителем и действительно частенько излечивал невротических больных. Постепенно его слава росла, но в столицах его еще не знали.

В 1900 году Распутин отправился в новое странствие в Киев. На обратном пути он несколько месяцев прожил в Казани, где познакомился с отцом Михаилом из Казанской духовной академии и приехал в Петербург к ректору духовной академии епископу Сергию (Страгородскому), очевидно, заручившись рекомендацией ректора Казанской духовной академии епископа Алексия (Молчанова). В дальнейшем именно Алексий закрыл дело по обвинению Распутина в хлыстовстве.

В 1903 году инспектор Санкт-Петербургской академии архимандрит Феофан (Быстров), являвшийся также духовником царской семьи, познакомился с Распутиным, представив его также и епископу Гермогену (Долганову). Сначала в Петербурге Распутин жил в монастырской гостинице, затем – в квартире протоиерея Иоанна Восторгова на Караванной, 11.

По словам Матрены Распутиной, Петербург отцу не понравился: «Потом он говорил мне, что ему душно здесь. Нежелание свое сразу уехать обратно объяснил так: «Меня держит здесь».

За Распутиным тянулась слава ясновидящего и целителя. Есть свидетельства, что он обладал необычайной силой внушения. Многие из его собеседников вспоминали его пронзительный, гипнотизирующий взгляд. Распутин брался лечить людей без всяких инструментов и лекарств. По меньшей мере в трех случаях, зарегистрированных высокопрофессиональными врачами, он оказал помощь пациентам, находившимся в почти безнадежном состоянии. Скорее всего, болезнь этих людей имела невротическое происхождение, чем и объяснялись успехи чудотворца-целителя.

По словам Матрены Распутиной, «отец никогда не скрывал, что бывал на радениях хлыстов, но точно так же он никогда не говорил, что разделяет их взгляды».

В 1903 году в Тобольскую консисторию поступило донесение от местного священника Петра Остроумова о том, что Распутин странно ведет себя с женщинами, приезжающими к нему «из самого Петербурга», об их «страстях, от которых он избавляет их… в бане»… о том, что в молодости Распутин «из своей жизни на заводах Пермской губернии вынес знакомство с учением ереси хлыстовской». В Покровское был отправлен следователь, но ничего порочащего он не обнаружил, и дело было сдано в архив. В Сибири совместные походы в баню мужчин, женщин и детей были обычным делом.

В 1904 году Распутин, очевидно при содействии архимандрита Феофана, переехал в Петербург, где стяжал у части великосветского общества славу «старца», «юродивого», «божьего человека», что «закрепляло в глазах петербургского света позицию «святого».