После освобождения Феликс живёт некоторое время в Ташкенте, где знакомится с архимандритом Борисом (Холчевым), и становится его духовным сыном. Хотя его грехи сексотства и убийства были совершены до крещения, Феликс исповедуется в них. Архимандрит Борис по поводу его стукачества сказал ему: «Ведь Вы были тогда убеждённым комсомольцем, это вы воспринимали как свой долг…». Рассказывал Феликс о. Борису и о звезде.
Феликс всегда с большой любовью вспоминал об о. Борисе. Он говорил, что по-настоящему у него был один духовный отец – архимандрит Борис.
Мне посчастливилось много лет спустя быть в Ташкенте и познакомиться с о. Борисом. От него исходило ощущение необычайного мира и спокойствия. Для меня он навсегда остался неким эталоном православного человека, живым критерием православности. Думается, эта встреча сыграла очень важную роль в моей духовной жизни.
Поселившись в Москве, Феликс знакомится с церковными людьми. Его принимают в доме А. В. Ведерникова, редактора Журнала Московской Патриархии. Он выступает с толкованием Апокалипсиса. Принимают его с большим воодушевлением. Действительно, говорить Феликс умел прекрасно. Кроме того, он обладал даром логического убеждения собеседника. О. Александр говорил про него: «Феликс может убедить в чём угодно». Своё прошлое Феликс не скрывал, но и не афишировал. И вот, вдруг в тех кругах, где его восторженно принимали, узнают, что он был стукачём и убийцей. Это производит впечатление шока. Нужно ещё ясно представлять себе, какое отношение было тогда к стукачам: страшнее стукача зверя нет. Кто-то отказывает ему в общении, но более спокойные и рассудительные вроде священников Александра Меня, Николая Эшлимана, Глеба Якунина, Димитрия Дудко продолжают поддерживать с Феликсом отношения, справедливо полагая, что всё это было в прошлом и к тому же ещё до крещения.
В это время происходит хрущёвское усиление гонений на Церковь. Священники Эшлиман и Якунин вместе с Карелиным пишут Открытые Письма Светским властям и Патриарху о бедственном положении Церкви в СССР и о противоречии этого положения советским же законам. Это было одно из первых правозащитных выступлений. И это был свободный голос гонимой Церкви. Письма писали собственно Эшлиман и Карелин. Глеб Якунин непосредственного участия в писании не принимал, но всё одобрял и подгонял в работе. Однако, было решено, что Феликс подписывать письмо не будет. Опасались, что его прошлое может как-то отрицательно повлиять на то, как письмо будет принято. Феликс согласился с этим, хотя впоследствии и очень об этом жалел. Подписали письмо два священника. Письмо было размножено и послано не только адресатам, но всем правящим архиереям Русской Церкви.
Письмо было восторженно принято многими церковными людьми, в том числе и некоторыми архиереями. Большой резонанс оно имело и на Западе, в частности в православных кругах. Сквозь глушилки по радио доходили до нас эти отзывы. Помню, один из зарубежных архиереев свой ответ на письмо надписал словами Тараса Бульбы: «Слышу сынку». Однако Патриарх вынужден был под давлением властей запретить священников Эшлимана и Якунина в священнослужении «за нарушение мира церковного». Священники подчинились решению Патриарха. Со стороны властей авторы Открытых Писем ожидали ареста. Их действительно вызывали в «органы», но арестовать не решились. Это был 1966 год.
В этом же году и была создана наша «подпольная духовная академия».
Итак, в начале октября 1966 года на квартире, которую снимал Л. Регельсон неподалёку от храма святителя Николая в Хамовниках, собрались о. Александр Мень, о. Николай Эшлиман, Феликс Карелин и мы, не так давно пришедшие в Церковь молодые тогда христиане. О. Александр отслужил молебен, представил нам Феликса как нашего преподавателя, а о. Николай напутствовал нас, сказав, что мы все, вероятно, ещё и не сознаём значение того дела, которое начато в этот день.
Полушутя, мы называли этот кружок подпольной духовной академией. В неё входило немного человек. Женя Барабанов, ставший впоследствии искусствоведом и философом, Миша Меерсон – Аксёнов, служащий теперь священником в Америке, Лев Регельсон, впоследствии автор известной книги: «Трагедия Русской Церкви» и диссидент, и я. Это был, так сказать, основной состав. Кроме нас время от времени приходили иногда и другие люди. Бывал, например, на наших занятиях Шурик Борисов, теперь – о. Александр, настоятель одного из московских храмов.