Перша письмова згадка про храм відноситься до 1582 року, у зв'язку з передачею міщанкою Гапкою Табковою у власність Троїцької церкві своєї садиби.

Під час панування у місті турків храм було перероблено на мечеть. На початку XVIII ст. з виходом турків з Кам'янця і встановленням польської влади храм був переданий греко-католикам. У 1722 році єпископ Афанасій Шептицький передав храм монахам ордену Св. Василія, які заснували при ньому монастир. Офіційною датою заснування вважається 22 травня 1722 р. Орден Василіян діяв при храмі до 1795 року. При ІІ розділі Польщі землі Кам'янеччини були включені до складу Росії. Разом з цим храм було переосвячено у православний.

У 1935 році у рамках боротьби радянського уряду із релігією храм було розібрано.

3 березня 1995 р. почалася віднова храму. Були проведені розкопки і дослідження фундаментів храму. 23 вересня 1996 р. Любомир Гузар заснував монастир. Першим настоятелем було призначено бр. Давида Кулинича, василіанина. З 1 вересня 2005 р. настоятелем монастиря було призначено о. Йосифа Будая. За п'ять років василіяни повністю закінчили відтворення будівлі та оздоблення храму і прилеглої території.

10 липня 2010 року Храм Пресвятої Трійці освятив Василій Семенюк — епископ Тернопільсько — Зборівський, УГКЦ.

Поземний план давньої будівлі був триконховий. За планом Троїцька церква була такою ж, як і Предтеченська та Петропавлівська. Зі сходу була одна півкругла абсида та з боків дві менші конхи. Західна частина була квадратною, всередені відділена від центральної аркою, та мала зверху дзвіницю. Довжина церкви без притвору становила 23,5 м і ширина без бічних конх 7,1 м. Склепіння над західньою частиною було хрестовим, а в середній частині півциліндрове, перерізане навпроти бокових конх меншим півциліндром. В вівтарі півциліндрове склепіння закінчувалося аркою і далі в апсиді півциліндер закінчувався конхою (четвертькулею). Впродовж 1672-1699 рр. Кам’янець-Подільський був під владою Османської Порти, тоді церкву було перетворено на мечеть та надбудовано 10-тиметровий мінарет, який, однак, після відходу турків було швидко розібрано. Василіани надбудували в 1749 дзвіницю. В 1854 над центральною частиною було перебудовано дерев'яну баню та покрито її замість гонту бляхою. В 1859 були збільшені вікна: мабуть продовжені до низу. Тоді ж до вівтаря добудовано ризницю та паламарню. В західній частині, з північного боку, були вхідні двері з кам'яними східцями. Біля північної та південої конхи було по два контрфорси. Під церквою знаходилися склепи з похованнями.