Dominikanie byli jednym z pierwszych łacińskich zgromadzeń zakonnych, jakie osiedliły się w Kamieńcu Podolskim. Klasztor św. Mikołaja w Kamieńcu Podolskim był drugą po Smotryczu fundacją dominikańską na Podolu, wspomnianą w dokumencie prowincjała polskiego Jana z Brzegu z 11 maja 1375 r. Bez wątpienia jednak data powstania klasztoru jest nieco wcześniejsza, ponieważ dokument wspomina konwent w Kamieńcu Podolskim już jako ważną dla rozwoju miasta instytucję.

Kiedy pierwszy, drewniany kościół spłonął, wybudowali w 1420 r. murowaną świątynię wraz z klasztorem. Od roku 1596 patronat nad kościołem pw. św. Mikołaja Bpa i klasztorem Dominikanów objęła rodzina Potockich, która kilkakrotnie finansowo wspierała odbudowę kompleksu klasztorno-kościelnego po zniszczeniach wywołanych pożarem w 1616 r., oraz dewastacjach, jakie nastąpiły podczas oblężenia miasta przez Turków w 1672 r. (pamiątką po czasach tureckich jest zabytkowa kazalnica - minbar). Kasata klasztoru miała miejsce w 1843 r. - kościół stał się świątynią parafialną.

Po zniszczeniach XX-wiecznych (kościół służył jako magazyn) i pożarze w 1993 r. zespół klasztorny jest odbudowywany przez OO Paulinów, którzy od 1998 r. są gospodarzami świątyni i klasztoru podominikańskiego.

Od 1999 r. w kościele podominikańskim w Kamieńcu Podolskim prowadzone są prace konserwatorskie, dofinansowywane ze środków Ministerstwa Kultury i Dziedzictwa Narodowego RP oraz Senatu RP.

Przeprowadzona została konserwacja prezbiterium, kamiennego, manierystycznego portalu oraz wykonano ekspertyzę konserwatorską łuku tęczowego. Sporządzona została też dokumentacja inwentaryzacyjna XVIII-wiecznej sygnaturki; obiekt wymaga rekonstrukcji po zniszczeniach powstałych podczas wichury, jesienią 2002 r. Prace konserwatorskie prowadzone były pod kierunkiem specjalistów z Wydziału Konserwacji i Restauracji Dzieł Sztuki Akademii Sztuk Pięknych w Warszawie.

W 2004 r. Ministerstwo Kultury i Dziedzictwa Narodowego, we współpracy ze Stowarzyszeniem „Wspólnota Polska”, finansowało kolejny etap prac konserwatorskich prowadzonych w kościele pw. św. Mikołaja Bpa, pod kierunkiem Janusza Smazy z Akademii Sztuk Pięknych w Warszawie. W zakres prac remontowo-konserwatorskich wchodził zakup materiałów koniecznych do wykonania zadania oraz zabezpieczenie ściany tęczowej tzn. oczyszczenie szczelin a także wypełnienie ich, częściowo pod ciśnieniem, spoiwem o zróżnicowanej granulacji.