Русский по происхождению, по всей вероятности, выходец из Малороссии. Прозвище Небоза означает «бедный», «убогий», «несчастный», «обездоленный». В послании императору Петру I сам Парфений подобрал к своему прозвищу синоним — «рабский».
Время выезда его из России, а также время и место принятия монашества неизвестно; первоначальной целью его выезда, вероятно, было желание посетить святые места. Эта цель сменилась стремлением оказать помощь русским христианам — турецким невольникам.
Длительное время он жил на Ближнем Востоке, много путешествовал, участвовал в освобождении русских пленников из турецкой неволи, для живших в Турции соотечественников совершал богослужения (для тех, кто «жаждет слышати слово Божие русским языком»).
Будучи чёрным священником, он путешествовал по восточным странам то на лошади или осле, пока были деньги, то пешком, когда обеднел, разыскивая единоверных по дальним селам и деревням, подвергаясь всяким невзгодам.
В 1686 году Парфений встретился в Константинополе со своим знакомым по Украине Иваном Лисицей, который приехал из Москвы вместе с послом Никитой Алексеевым и переводчиком Авраамом к Константинопольскому патриарху Дионисию за грамотами, санкционирующими подчинение Киевской митрополии русскому царю и строительство в Константинополе церкви Иоанна Предтечи. Парфений показывал приезжим город, водил их в Софийский собор, куда «с великою трудностию и платежем входят христиане», а также договорился о том, чтобы освобожденные им православные отправились с посольством в Россию. Сам Парфений тоже решил ехать с ними в Москву, однако доплыл только до Очакова, где посольство было задержано, и ему пришлось через Белгород-Днестровский возвращаться обратно на Восток.
Константинопольский патриарх Каллиник настолько уважал русского инока, что в 1691 году хиротонисал его во епископа с возведением в сан митрополита Лаодикийского (Антиохийский патриархат). Кизический митрополит Кирилл, оставаясь при патриархе в Константинополе, послал Парфения вместо себя на свою Кизическую кафедру, где Парфений находился около двух лет, поэтому он иногда называется митрополитом Кизическим.
В 1696 году Парфений наконец добрался до России. По возвращении в Москву он в 1698 году преподнёс императору Петру I панегирик по поводу победы над турками. Даровитый и энергичный малоросс понравился государю, и в 1701 году он был рукоположен митрополитом в незадолго перед тем завоёванный Азов, долженствовавший, по предположению Петра Великого, явиться центром новой епархии. Однако учреждение Азовской митрополичьей кафедры не осуществилось, и Парфений в Азов так и не поехал.
3 декабря 1703 года назначен митрополитом Холмогорским и Важеским. Святитель отправился к месту своего назначения в декабре 1703 года, но по дороге, остановившись в Ярославском Спасо-Преображенском монастыре, тяжело заболел и 2 января 1704 года скончался.
Погребён в Печерской церкви под колокольней Спасо-Преображенского монастыря в Ярославле. Над могилой его поставлена деревянная рака, в которой прежде почивали мощи благоверных князей Феодора, Давида и Константина, Ярославских чудотворцев.
Известность писателя Парфению доставили следующие его произведения: письмо к Петру Великому, панегирик в стихах Петру Великому по случаю победы под Азовом (На победу злочестивого Мустафы, султана турецкого), стихи патриарху Геннадию, символ или изъяснение утвари и сосудов церковных (рукопись Синодальной библиотеки, № 140) и перевод надписи на гробе Константина Великого «Како иногда победится злочестивый султан турский».