Редемптористи розпочали свою працю в м.Кам'янці-Подільському в 1991 р. У 1993 р. ченці отримали від держави під свій монастир дім панства Чарторийських (XVI-XIX ст.). Парафія св. Йосафата, якою опікуються отці, розташована в історичній частині міста, де, окрім нашого храму, є також два храми Римо-Католицької Церкви з осідком правлячого єпископа, один - громади Православної Церкви Московського Патріархату, а також вірменський храм, який на даний час не функціонує. Неподалік від подвір'я церкви розташована фортеця, котру єднає з містом старовинний міст.

Редемптористи працювали в Кам'янці-Подільському й раніше. Вже в 1942 р. о. Василь Величковський працював у церкві св. Миколая, але німецька влада вигнала його з міста. Восени 1962 р. до міста приїхав о. Євстахій Смаль, який виконував священичі обов'язки у римо-католицькому храмі св. Миколая. Люди пам'ятають отця як надзвичайно добру, скромну, чутливу людину. Під час сповіді він допомагав людям пізнати свій духовний стан і виправити його. У своїй маленькій кімнаті о. Євстахій за шафою мав скромний престіл, де відправляв Службу Божу за Греко-Католицьким обрядом. Цей престіл знайшли під час обшуку, і наприкінці травня 1964 р. о. Євстахію було наказано виїхати з міста.

Завдяки праці підпільних отців на початку 90-их років у Кам'янці-Подільському вже існувала сформована греко-католицька громада. Влада віддала греко-католикам храм св. Йосафата, в якому до того був обласний архів. Стараннями о. Михаїла Колтуна, який тепер є Сокальсько-Жовківським єпископом, 3 листопада 1990 року редемптористи вперше відправили Літургію у вагончику, розташованому на місці церкви оо. Василіян, що її зруйнували комуністи. Там протягом цілої зими відправляли о. Михайло Колтун, о. Мар'ян Ференц, о. Ігор Цар, а тим часом готували до Богослужінь будівлю храму. З 26 квітня 1992 р., після закінчення ремонту, храм почав регулярно функціонувати. 8 листопада 1992 р. владика Филимон Курчаба урочисте посвятив храм св. Йосафата.

У Кам'янці-Подільському залишився працювати о. Ігор Цар, а 1 липня 1996 р. до міста приїжджають о. Петро Мірчук  і о. Євген Задорожний і розпочинають старанно працювати над духовним зростанням парафії: відправляють Богослужіння, сповідають, відвідують хворих, проводять реколекції.

Рішення про передачу редемптористам дому Чарторийських було прийнято 18 березня 1993 р., але лише 24 грудня 1996 р. Державний Комітет України у справах релігії офіційно оформив потрібні документи. 23 вересня Екзарх Києво-Вишгородський Любомир Гузар благословить монастир під іменем св. Кирила і Методія. Під керівництвом настоятеля було відновлено монаший дім і церкву.

Деякий час о. Петру Мірчуку допомагали також о. Микола Коваль і бр. Богдан Гелета. о. Євген Задорожний,  працював в іншій церкві, на новому житловому масиві.

Від початку листопада 2006 року в Кам'янці-Подільському разом з редемптористами працюють також сестри Місіонерки Найсвятішого Ізбавителя (редемптористки). Поле праці сестер є досить великим. Передусім це катихиза, праця з дітьми та молоддю. 

Настоятелі монастиря свв. Кирила і Методія:

• Мірчук Петро 4 липня 1996 – 28 червня 2002
• Вітовський Володимир 26 серпня 2002 – 7 червня 2005
• Горбань Іван 7 червня 2005 – 23 вересня 2005
• Кашуба Олег 23 вересня 2005 – 6 березня 2011
• Ковбель Сергій 6 березня 2011 – 13 травня 2014
• Котик Віталій 13 травня 2014 - 15 березня 2017
• Павлій Ігор 15 березня 2017 - 15 лютого 2019
• Олещук Віталій 15 лютого 2019 - 24 лютого 2021
• Банга Юрій 25 лютого 2021 -

Спільнота монастиря