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

Распутин впервые появился в Петербурге в 1903 или 1904 г. Хотя ему было около 40 лет, он называл себя «старцем» — этого неканонического ранга обычно удостаивались особо уважаемые, преклонного возраста монахи. За Распутиным тянулась слава ясновидящего и целителя. Есть свидетельства, что он обладал необычайной силой внушения. Многие из его собеседников вспоминали его пронзительный, гипнотизирующий взгляд. Распутин брался лечить людей без всяких инструментов и лекарств. По меньшей мере в трех случаях, зарегистрированных высокопрофессиональными врачами, он оказал помощь пациентам, находившимся в почти безнадежном состоянии.

Распутину протежировали высокие церковные иерархи, в том числе ректор столичной духовной академии Феофан и саратовский епископ, член Святейшего синода Гермоген. Они ввели «старца» в аристократические гостиные, где он, по своим собственным словам, вел себя как простой «мужик в смазных сапогах, разгуливавший по паркетам». Распутин носил одежду крестьянского покроя (но из дорогих тканей), руками брал еду с тарелки и т. д. Нарушение правил этикета не мешало ему заводить все более высокие знакомства и, наконец, вступить в контакт с представителями императорской фамилии. Таинственного сибиряка «открыли» великие княгини Стана и Милица, дочери черногорского владыки, породнившиеся с династией Романовых. Они представили Распутина великому князю Николаю Николаевичу (младшему), а потом своими рассказами о чудесах вызвали интерес у царской четы.

Первая встреча Николая II с Распутиным произошла 1 ноября 1905 г. В тот день царь записал в своем дневнике: «Познакомился с человеком Божьим Григорием из Тобольской губернии». Встречи стали регулярными. Когда Распутин бывал в столице, он посещал царскую резиденцию и вел возвышенные беседы. К ужасу придворных, он фамильярно называл Николая II «папашей», а Александру Федоровну «мамашей». Они же уважительно именовали его «Наш друг» и в письмах упоминали о нем только с прописной буквы. Под воздействием то ли реальных фактов, то ли случайных совпадений Николай II и Александра Федоровна уверовали, что молитвы «старца» могут облегчить страдания наследника престола Алексея, больного гемофилией.