Католицька Церква латинського обряду прийшла на Поділля завдяки діяльності домініканського та францисканського орденів, місії яких свого часу підтримували польський король Казимир ІІІ і подільський князь Олександр Коріятович.
Точна дата заснування дієцезії невідома, але деякі джерела вказують, що вона припадає на на час правління Папи Урбана VI (1378–1389). Перша вагома згадка про Кам’янець-Подільську дієцезію з єпископом датована 1406 роком. Тоді вона належала до Галицької митрополії, осередок якої 1412 року перенесли до Львова. Точні кордони дієцезії були визначені лише 1717 року, та припускають, що на початку її межі збігалися з кордонами Подільського князівства.
Протягом XV–XVIІ століть на території дієцезії активно поставали храми й росли парафіяльні спільноти. Для розбудови релігійного життя були запрошені члени чернечих родин: бенедиктинці (XV століття), францисканці й кармеліти (XVІІ століття), а в епоху контрреформації – єзуїти. Але нестабільність кордонів і політичної ситуації заважали плідному душпастирству, особливо під час окупації Османською імперією (1672–1699).
1721 року єпископ Стефан Рупнєвський (1716–1721) заснував духовну семінарію. Трохи раніше, 1717 року, він уперше встановив точні межі дієцезії та впровадив поділ на деканати: Дунаєвецький, Язловецький, Сатанівський і Меджибозький. За час його правління кількість парафій зросла до 39.
До моменту, коли більша частина Кам’янець-Подільської дієцезіїї опинилась у межах Російської імперії, на її території виникали братства й парафіяльні школи, була відреставрована катедра.
У часи панування Російської імперії дієцезія пережила дві ліквідації (1793–1795 та 1866–1919), яких Апостольський Престол, по суті, не визнав. Під час другої з них царська влада ліквідувала Кам’янець-Подільську дієцезію, приєднавши її до Луцько-Житомирської. Лише внаслідок порозуміння між Російською імперією та Апостольським Престолом, укладеного 1882 року, Кам’янець-Подільську дієцезію було відновлено у вигляді апостольської адміністрації, що залишилася під опікою Луцько-Житомирських єпископів. Із 1930 року дієцезіальна адміністрація фактично перестала існувати.
Відновлюючи структури Римсько-Католицької Церкви в Україні, 16 січня 1991 року Папа Йоан Павло ІІ відновив і Кам’янець-Подільську дієцезію. Вона простягалася на території десяти областей, від Збруча на заході й до кордонів із Росією на сході, охоплюючи також Крим. Її площа становила 270 700 км2. Першим єпископом став Ян Ольшанський (1991–2002; відійшов у вічність 23 лютого 2003 року).
2002 року Папа Йоан Павло ІІ реорганізував церковні структури латинського обряду в Україні, виділивши зі складу Кам’янець-Подільської дієцезії Одесько-Сімферопольську і Харківсько-Запорізьку дієцезії, і встановлюючи нові межі Кам’янець-Подільської, яка тепер охоплювала Хмельницьку й Вінницьку області (47 158 км²).
4 травня 2002 року Кам’янець-Подільську дієцезію очолив єпископ Леон Дубравський, який від 1998 року виконував обов’язки єпископа-помічника на цій території.
2006 року єпископом-помічником Кам’янець-Подільської дієцезії було призначено отця Яна Нємєца (помер 2020 року). 2012 року дієцезія збагатилася ще на одного єпископа-помічника, яким став отець Радослав Змітрович ОМІ.
Площа дієцезії: 47 100 км2.
Області, які належать до Кам’янець-Подільської дієцезії: Хмельницька, Вінницька.
Кількість вірних: 200 000.
Кількість священиків: 113 дієцезіальних, 80 чернечих.
Кількість орденів та згромдажень: 22 + 4 жіночих, 14 чоловічих.
Кількість деканатів: 10.
Кількість парафій: 246.
Сайт дієцезії: https://www.camenecensis.org
Курія Кам’янець-Подільської дієцезії РКЦ: 32301, м. Кам’янець-Подільський,
вул. Францисканська, 2, тел.:+380 (3849) 9-11-57; е-mail: curiapodole@gmail.com.
Катедральний храм: собор святих Петра і Павла в Кам’янці-Подільському (реконсекрований 1998 року).
Патрональне свято дієцезії: урочистість Матерії Божої Летичівської (6 липня).