La iglesia fue construía en tiempos del obispo Jakuba Buczacki en el siglo XVI en estilo renacentista (la construcción de la iglesia de piedra se atribuye al obispo Pablo de Bojańczyce).^[5]​ En los años 1646 a 1648 fue reconstruida en estilo barroco. En 1672, durante la ocupación turca de estas tierras, el templo fue transformado temporalmente en mezquita y se construyó un minarete.^[6]​

Dejar el minarete y la media luna en la torre era una condición estipulada en la paz de Karlowitz firmada el 26 de enero de 1699, aunque volvió a ser catedral ese año.^[7]​ Para preservar las disposiciones del tratado y al mismo tiempo eliminar el símbolo humillante del dominio otomano, se colocó en la parte superior una figura de madera, que el 10 de mayo de 1756, gracias al obispo Michał de Dębowa Góra Dembowski fue sustituida por una figura de Nuestra Señora de cobre, traída de Gdańsk,. En la mitad del siglo XVIII, la catedral fue reconstruida en estilo barroco tardío. El altar fue financiado por Stefan Rupniewski y Michał Dembowski financió una nueva sillería, un púlpito, confesionarios y un órgano. También se construyó una nueva fachada de la catedral, terminada en 1754.

Según el decreto del zar Alejandro II del 5 de junio de 1866, la diócesis de Kamianets-Podilski fue abolida y unida a la diócesis de Lutsk-Zhitómir.

En abril de 1922 los soviéticos saquearon los tesoros de la catedral. El 14 de mayo de 1936 las autoridades comunistas cerraron el templo y lo transformaron en un museo.

Temporalmente estuvo abierta desde el verano de 1941 al 4 de junio de 1945, mientras duró la ocupación alemana en la Segunda Guerra Mundial. En los años 1946-1990 la iglesia albergaba un "museo del ateísmo". El 13 de junio de 1990 fue devuelta a los fieles católicos, y el 29 de junio de ese mismo año se celebró la primera misa.^[8]​

La iglesia es de tipo basilical de tres naves. Los muros son de mortero de piedra caliza.

El minarete con la escultura de la Virgen María fue construido por constructores turcos sobre los cimientos de una capilla renacentista y tiene 40 metros de altura. La escultura de la Virgen María, instalada en lo alto del minarete tras la expulsión de los turcos en 1756, es de estilo barroco y está realizada de aleaciones de cobre y plata. El arco triunfal tiene una planta casi cuadrada, se asemeja a una puerta magnífica y el pasaje tiene un arco de medio punto. Las fachadas están decoradas con pilastras de orden jónico y un entablamento abierto. El edificio está coronado por una linterna arquitectónica de forma barroca con volutas, una de las mejor conservadas de Ucrania.

•  
  Vista de la catedral en 1871
•  
  Minarete y fachada de la catedral
•  
•  
  Altar principal de la catedral
•  
  Tumbas en la cripta de la catedral

• Iglesia católica
• Catedral de San Pedro y San Pablo

• Жарких М. І. Храми Поділля. Довідник. (Місто Кам'янець-Подільський)
• Кафедральний костьол святих Петра і Павла // Кам'янець-Подільський. Туристичний путівник. — Львів : Центр Європи, 2007. — C. 156—166.
• Юрков Василь, Юркова Галина. 7 чудес Кам'янця-Поділлі (дійсність і легенди). — Кам'янець-Подільський, 2010. — 56 с.
• Karol Iwanicki Katedra w Kamieńcu . — Warszawa, 1930.
• Петропавловского кафедрального костела ансамбль, XVI—XVIII // Памятники градостроительства и архитектуры Украинской ССР. в 4-х томах (за ред. Жарікова Н. Л.). — К. : Будівельник, 1983—1986 (електронна версія). — Т. 4. — С. 172.
• Шутко О. Османські пам'ятки Кам'янця-Подільського: вісті з минулого // Дзеркало Тижня.  — Вип. № 32, 4 вересня 2015 року.
• Шутко О. Хатідже Турхан: Історичний роман: Кн.3 : Султана-українка — покровителька козаків  — Тернопіль: Навчальна книга — Богдан, 2019. — 400 с.