В ансамблі вдало поєднались риси архітектурних стилів: ренесансу, бароко, неоготики. Костел тринавовий, базилікальний з довгим пресбітерієм,трьома ренесансними каплицями та високим притвором. До західного фасаду прибудований мінарет з тесаних білокам’яних блоків,основою якого слугує каплиця 16 ст. Пізніше на верхівку мінарету встановлено дерев’яну скульптуру Діви Марії, котру в 1756р. замінено на іншу,зі сплаву міді й срібла. В 1842-1855 р.р. до південного фасаду прибудовано паперть в псевдоготичному стилі.
Засновниками першого дерев`яного костьолу, що був побудований близько 1370р., були литовські князі Коріатовичі, що правили в той час Поділлям. А вже через 5 років на прохання польського короля Папа Римський Григорій XI засновує в Кам`янцю диецезию, і костьол стає кафедральним.
Будівлю кам`яного костьолу приписують єпископові Якову Бучацкому (1502-1517), людині релігійній й багатій. Костьол був побудований у романському стилі, мав три нефи. Вівтар був орієнтований на захід і перебував у тім місці, де зараз вхід. А в той час вхід у костьол був з боку Польського ринку.
У середині XVI століття єпископ Леонард Слончевський (1547 - 1562) пристроює каплицю Пресвятих Таїнств із півночі, а з південно-заходу каплицю Розради Пренепорочної Богородиці. До нашого часу на одному з контрфорсів збереглася кам`яна таблиця з гербом і буквами "L.S.Е. З" ( Леонард Слончевский єпископ Камянецький), по сторонах дата 1561 імовірно, це рік освячення каплиці.
Єпископ Павло Волуцький (1591-1607) побудував кам`яний будинок єпископа. В 1616 році пожежа сильно зашкодила костьол, але через 5 років у ньому вже відбулося врочисте богослужіння із приводу перемоги над турками під Хотином. Єпископ Павло Пясецкий (1627- 1640) побудував каплицю Непорочного Зачаття Богородиці. В 1644 р. єпископ Михайло Дзялинський прибудував зі східної сторони презбитеріум, перенесучи туди Головний Вівтар. Презбитеріум побудований у готичному стилі. У той же час із боку Польського ринку, за вівтарем установлюється "Сад Гефсиманский". У період турецького панування (1672-1699) єпископи перебували за межами Поділля, і тут майже не було католиків. Кафедральний костьол став головною мусульманською мечеттю. Із західної сторони пристроюється мінарет висотою 36,5 м, основою якого стала каплиця XVI століття у вигляді куба, закладене каменями, а зверху встановлена двадцатиметрова вежа з 145 кам`яними щаблями. Все оздоблення костьолу було знищено, вивезене за місто кістки християн, які були поховані на цвинтарі костьолу. Після повернення Подолии до складу Польського королівства, єпископ Ян Гнинский переосвячує мечеть у костьол. Про цю подію свідчать дві пам`ятні плити на пілонах у центральному нефі.
У середині XVIII століття єпископ Микола Дембовский (1740-1757) і архітектор Ян де Вітте проводять капітальний ремонт: споруджується новий вівтар, установлюються крісла каноніків, амвон прикрашається скульптурами Євангелістів. Головний фасад прикрашається пілястрами, капітелями, скульптурами. Гармонія й цілісність фасаду доповнюється гербом єпископа Н. Дембовского й пам`ятною плитою, текст на якій говорить: "З волі Добродії шляхетному Миколі з Гори Дубової Дембовскому єпископові Камянецькому обновникові святині від вдячної капітули ця плита встановлена в 1754 р. " Ремонт мінарету й установка мідної статуї Богородиці висотою 3,5 м також заслуга Миколи Дембовского. Статуя була виготовлена в Гданьске й установлена 10 травня 1756 року під дзвін і стрілянину гармат у замку. Богородиця коштує на земній кулі й півмісяці, благословляючи місто й край. Навколо голови ореол з 12 зірок. На згадку про цю подію в нижній частині мінарету був вибитий напис: "Богородиця, Непорочна Діва, Покровителька міста. Фігура встановлена при Миколі герба Елита Дембовском, єпископі Кам`янець - Подільському, абаті Хутр[ецком], кавалері ордена Білого Орла в 1756 р. " Указом від 6 вересня 1795 . без узгодження з Апостольською Столицею імператриця Катерина II ліквідувала диецезию. Але вже в 1798 році, після угоди імператора Павла I з Папою Римським Пием VI, дієцезія була відновлена. У червні 1820 року блискавка вдарила в мінарет, виникла пожежа, що швидко був погашений.
9 квітня 1823 року під час урагану фігура нахилилася в східному напрямку, виникла погроза падіння Богослужіння тимчасово було перенесено в Домініканський костьол. Ремонтні роботи були проведені під керівництвом ксьондза Учти. І 25 липня 1823 року була відправлена перша служба Божа.
З 1853 по 1860 р. у костьолі проводився капітальний ремонт. У цей час були обновлені вівтарі, установлений орган австрійської фірми "Карл Хессе", у презбітріумі вставлені вікна з кольоровими стеклами. Каплиця Непорочного Зачаття Богородиці була розписана темперним живописом італійським майстром Джовані Сампіні. У ніч із 29 на 30 червня 1862 р. пожежа знищила весь дах костьолу. На поновлення святині люди жертвували останні гроші, персні, намиста. Надавали допомогу й представників інших конфесій. І вже 7 грудня 1862 р. єпископ Антоній Фіалковський відправляв урочисте богослужіння в костьолі. Указом імператора Олександра II від 5 липня 1866 р. Кам’янецка діецезія була ліквідована й приєднана до Луцько-Житомирського. Єпископ А. Фіалковский залишив місто. Костьол став парафіяльним.
В 1918 р. Папа Римський Бенедикт XV відновив Кам`янець - Подільську дієцезію, а єпископом призначив пробоща (настоятеля) ксьондза Петра Маньковского. Через два роки більшовики ліквідували дієцезію. Костьол стає парафіяльним, а в 1936 році був закритий. В 1941-1946 р. костьол був діючим. В 1946 р. його закривають, мотивуючи тим, що до XVII століття тут було православна церква.
З 1946 р. по 1990 р. у костьолі розміщався відділ атеїзму історичного музею. 29 червня 1990 р. на прохання віруючий костьол був повернутий римо-католической громаді. 16 січня 1991 р. Папа Римський Іоанн-Павло II призначив ксьондза Яна Ольшанского єпископом Кам’янецким і тим відновив дієцезію. 10 червня 1995 року в Кафедральному костьолі був освячений на єпископа-помічника ксьондз Станіслав Падевський.
До комплексу споруд Кафедрального костелу св.ап.Петра і Павла входять : Кафедральний костел св.ап. Петра і Павла з каплицями – Святих таїнств, Непорочного зачаття Діви Марії, Утішення Діви Марії; дзвіниця, тріумфальні ворота, Турецький мінарет, будинок подільського єпископа.
