Перша письмова згадка про храм відноситься до 1582 року, у зв'язку з передачею міщанкою Гапкою Табковою у власність Троїцької церкві своєї садиби.
Під час панування у місті турків храм було перероблено на мечеть. На початку XVIII ст. з виходом турків з Кам'янця і встановленням польської влади храм був переданий уніатам. У 1722 році єпископ Атанасій Шептицький передав храм монахам ордену Св. Василія, які заснували при ньому монастир. Офіційною датою заснування вважається 22 травня 1722 р. Орден Василіян діяв при храмі до 1795 року. При ІІ розділі Польщі землі Кам'янеччини були анексовані Росією. Разом з цим храм було переосвячено у православний.
У 1935 році у рамках боротьби радянського уряду із релігією храм було розібрано.
3 березня 1995 р. почалася віднова храму. Були проведені розкопки і дослідження фундаментів храму. 23 вересня 1996 р. кардинал Любомир Гузар заснував монастир. За п'ять років василіяни повністю закінчили відтворення будівлі та оздоблення храму і прилеглої території.
10 липня 2010 року Храм Пресвятої Трійці освятив Василій Семенюк — єпископ Тернопільсько-Зборівський, УГКЦ. Архітектором, який розробив проект відновлення храму, є Володимир Бевз.
На церковному мурі – мозаїчний триптих: Богородиця з архангелами Гавриілом і Михаілом, які захищають місто.
Pirmasis raš ytinis baž nyč ios paminė jimas datuojamas 1582 m. , susiję s su miestieč io Gapkos Tabkovos perdavimu jo dvaro Trejybė s baž nyč ios nuosavybė n.
Mieste valdant turkams, š ventykla buvo paversta meč ete. XVIII amž iaus pradž ioje. turkams pasitraukus iš Kamianecų ir į sigalė jus lenkų valdž iai, baž nyč ia perduota unitams. 1722 metais vyskupas Atanasijus Š eptytskis baž nyč ią perdavė Š v. Bazilijaus ordino vienuoliams, kurie joje į kū rė vienuolyną . Oficiali į kū rimo data – 1722 m. geguž ė s 22 d. Bazilijonų ordinas baž nyč ioje veikė iki 1795 m. Antrojo Lenkijos padalijimo metu Kamianec-Podilskio ž emes aneksavo Rusija. Tuo pat metu baž nyč ia vė l buvo paš ventinta stač iatikių baž nyč iai.
1935 m. , kai sovietų valdž ia kovojo su religija, baž nyč ia buvo iš montuota.
1995 metų kovo 3 dieną baž nyč ia pradė ta restauruoti. Vyko š ventyklos pamatų kasinė jimai ir tyrimai. 1996 m. rugsė jo 23 d. kardinolas Lubomiras Husaras į kū rė vienuolyną.
Per penkerius metus bazilijonai visiš kai už baigė pastato rekonstrukciją ir š ventyklos bei apylinkių puoš ybą.
2010 m. liepos 10 d. Š ventosios Trejybė s baž nyč ią paš ventino Ternopilio-Zborivo vyskupas Vasyl Semenyuk, UGCC. Baž nyč ios restauravimo projektą parengę s architektas yra Volodymyras Bevzas.
Ant baž nyč ios sienos – mozaikinis triptikas: Mergelė su arkangelais Gabrieliumi ir Mykolu, kurie saugo miestą .