По дороге из-за болезни ему пришлось надолго остановиться в раскольническом Мануиловском ските в Молдавии, на расстоянии 100 верст от города Яссы, недалеко от города Фэлтичени. Именно здесь Господь сподобил его освободиться от давно мучившего его совесть тяжелого груза – раскольничества. Очищенный и жаждущий чистого источника – Православия, он со своими единомышленниками – новообращенными друзьями отправился в православный Нямецкий монастырь – наследие великого старца Паисия (Величковского).
Укрепившись здесь в истинной вере, они отправились в Россию для ознакомления с учением и повседневной жизнью Русской Православной Церкви. В июле 1837 года прибыли в Киево-Печерский монастырь. Вот как описывает свои новые впечатления отец Парфений: «В течение многого времени, которое мы провели в Киеве, ежедневно мы посещали святые места, пещеры и лобызали мощи святых угодников Божьих. Делали это не так, как прежде в расколе, грустно, темно и мрачно, но светло, весело и радостно. Нам казалось, что все кругом благо и приятно, все приводило нас в умиление и слезы».
Из Киева отец Парфений отправился в Нижний Новгород, в Высоковский единоверческий монастырь, где жил под руководством великого старца Тимона. Довольно подготовившись, отец Парфений с друзьями вернулся в Молдавию, в православный монастырь Ворону, где над ним было совершено таинство мνропомазания. Как вспоминал впоследствии отец Парфений: «Архимандрит приказал всем нам снять с себя раскольническую монашескую одежду, после чего на нас надели послушническую. Потом духовник всех исповедал и испытал совесть каждого, кто кем и как был крещен. Потом семь дней препроводили мы в посте и молитве, проклиная все ереси и расколы. На восьмой день всех нас, десять человек, присоединили к Единой Святой Соборной Апостольской Христовой Церкви: одних снова крестили, других только помазали святым мνром. Затем всех причастили Святых Таин Тела и Крови Христовой... потом объявили нас послушниками и причислили к братству».
Радости отца Парфения не было границ. Но старая заветная мечта об Афоне не оставляла его. Вскоре он решил во что бы то ни стало добраться до Святой Горы. И, наконец, 8 ноября 1839 года прибыл на давно желанный Афон.
Жил в келлии у старца Арсения. Потом по его благословению некоторое время подвизался один. После чего спасался у старца Иеронима (Соломенцова) в келлии пророка Илии Ставроникитского монастыря, где по благословению отца Арсения был пострижен в мантию с именем Памва.
Он очень полюбил своего нового старца – отца Иеронима. Вот что он пишет об этом: «И возлюбила душа моя его, поэтому считал за великую потерю, если не видел его несколько часов и не слышал от него полезного слова... И положил я намерение: никогда не разлучаться с ним, даже до смерти». С отцом Иеронимом вместе 20 октября 1840 года он переехал в Руссик.
В 1841 году был пострижен в схиму с именем Парфений в Русском Пантелеимоновом монастыре. Постригал его духовник Иероним, а подводил игумен Герасим. «О, какой я исполнился неизреченной радости, – говорил отец Парфений, – яко сподобился принять великий иноческий образ в жребии Царицы Небесной на Святой Горе Афонской и в великой царской русской обители святого великомученика Пантелеимона!»
Но недолго продолжалась радость отца Парфения. Вот как он описывает новый поворот в своей жизни: «Видимо, Царь Небесный не хочет, чтобы мы радовались, живя в этой маловременной жизни. Поистине
От духовника Иеронима отец Парфений получил благословение ехать в Россию для сбора пожертвований в пользу обители. 8 апреля 1841 года, после полутора лет пребывания на Афоне, он был вынужден, следуя благословению, оставить удел Божией Матери. Возвратился он только через три года. В 1845 году побывал в Иерусалиме. Свои приключения и впечатления во время пребывания на Афоне и во время поездки по России и в Иерусалим он описал в книге «Сказание о странствии и путешествии по России, Молдавии, Турции и Святой Земле», которая была издана в 4-х частях в 1855 и 1856 годах. Эта книга является обильным источником по истории Афона, русских обителей и для жизнеописаний многих выдающихся подвижников Святой Горы.
В мае 1846 года отец Парфений вернулся на Афон и уже не застал в живых своего первого духовника отца Арсения. Прожив там еще шесть месяцев, по благословению старцев обители вновь был послан в Россию, где опять занимался сбором пожертвований.