Дзвіниця є невіддільною частиною соборного комплексу й розташована у північно-східному куті ділянки, на якій височіє латинська катедра Святих Апостолів Петра і Павла в Кам’янці-Подільському. Її будівництво розпочалося у зв’язку з розширенням катедрального храму за понтифікату єпископа Павла Домініканця (1434–1453), тобто після приєднання Кам’янця разом із Поділлям до Корони Польської. У межах цієї перебудови до наявного корпусу добудували пресвітерій, а також розпочали зведення окремої вежі, яку завершили наприкінці XV століття. У той час дана споруда виконувала передусім оборонну функцію, утворюючи разом із готичними дзвіницями церков Святої Трійці та Святого Івана Хрестителя, а також вірменського костелу Святого Миколая важливий елемент міської оборонної системи, чітко окреслений у панорамі Кам’янця.

Збудована з каменю, квадратна в плані (12,7 × 12,7 м), вежа вирізнялася масивними мурами, що уступчасто звужувалися до верху. Їх товщина біля основи перевищувала 3 м, що чітко вказує на первісне оборонне призначення споруди. Дзвіниця мала два входи: один розташовувався у приземній частині південної стіни й вів до невеликого приміщення зі склепінням у формі бочки; другий – у західній стіні, на висоті близько 6 м над рівнем землі, який забезпечував безпосередній доступ до другого ярусу. До цього входу вели зовнішні дерев’яні сходи, які у разі небезпеки можна було легко демонтувати. Таке рішення було типовим для середньовічних житлово-оборонних веж, відомих у Франції як донжони, а в Центрально-Східній Європі – як стовпи. Два найнижчі яруси вежі були перекриті склепіннями, тоді як три верхні – балковими перекриттями. Сполучення між другим і третім ярусами забезпечували сходи, влаштовані в товщі муру, тоді як доступ до інших рівнів здійснювався дерев’яними сходами, опертими на внутрішні уступи. Четвертий поверх використовувався для підвішування дзвонів, з високими склепінчастими вікнами, по одному з кожного боку, що забезпечували вільне поширення звуку. П’ятий, найвищий ярус мав оборонний характер: його обладнали машикулями з бійницями та навісними бартізанами в кутах. Вежу завершував високий шатровий дах із люкарнами.

Після 1699 року, коли Кам’янець разом із Поділлям повернувся до складу Речі Посполитої після турецької окупації, функція вежі змінилася з оборонної на суто релігійну. У середині XVIII століття оборонні елементи було ліквідовано. Уявлення про первісний вигляд найвищого ярусу дає дзвіниця при вірменському костелі Святого Миколая в Кам’янці-Подільському, що датується тим же періодом, також п'ятиповерхова і подібна за висотою до вежі собору (22,7 метра проти 24 метрів). Готичний характер дзвіниці перед бароковою перебудовою зафіксовано на плані-гравюрі Кам’янця-Подільського, виконаному Кипріаном Томашевичем після 1672 року.

Модернізацію дзвіниці було проведено у 1755–1757 роках, за часів правління єпископа Миколая Дембовського, який ініціював реставрацію собору, доручивши його перебудову Яну де Вітте (1709–1785 рр.), місцевому військовому архітектору. З цього часу походить також бароковий фасад храму, завершений у 1754 р., та позолочена статуя Богоматері, відлита у Гданську та встановлена на мінареті 10 травня 1756 р. Саме необхідність розміщення цієї скульптури, висотою 3,5 м, на висоті 37 м та встановлення її на спеціально підготовленому постаменті, що увінчує мінарет, спонукала єпископа до перебудови дзвіниці. Вежу, що знаходилася на відстані 40 м від мінарету і була розташована з того ж боку собору, надбудували, зрівнявши її за висотою з мінаретом і дозволивши побудувати між ними дерев'яний міст – своєрідну естакаду. Важку статую перенесли на верхній поверх дзвіниці; її транспортування полегшило попереднє знесення склепіння між другим і третім поверхами. Потім статую підняли на платформу, яку за допомогою блоків і канатів підтягли та встановили на мінарет. Здійснена операція стала доказом видатних технічних умінь, автором яких, як вказує Ольга Пламєніцька, був також Ян де Вітте.

Унаслідок надбудови було усунуто елементи, що свідчили про первісний оборонний характер вежі, замінивши їх архітектурною артикуляцією, типовою для бароко. Декор зосереджено виключно на двох найвищих ярусах, тоді як нижні частини залишили гладкими. Таке рішення було виправданим, адже зблизька вони не були помітні, а здалеку – понад дахами будинків – сприймалася лише верхня частина споруди. Єдиним мотивом, присутнім на всіх рівнях вежі, залишилося наріжне рустування. Готичні вікна заввишки 7 м, розташовані на передостанньому ярусі, було замуровано. На їхньому місці влаштовано сліпі аркади, що підтримуються тосканськими пілястрами, фланковані поодинокими композитними пілястрами - подібними до тих, що розчленовують фасад собору. Над ними проходить злегка заламаний антаблемент, який плавно переходить у бази пілястр останнього поверху. Найвищий ярус так і не було добудовано на повну висоту через смерть фундатора, про що свідчать вали пілястр, позбавлені капітелей. Між ними, на кожному фасаді, розміщено великі прямокутні вікна з лиштвами з «вушками». На нижчому ярусі, в арковій ніші, влаштовано по два отвори: прямокутний унизу та круглий вище, обидва обрамлені кам’яними лиштвами. Саме на цьому рівні підвішено дзвони, яких було шість. Три з них належали до первісного обладнання катедри. Найстарішим був дзвін святого Стефана, фундований у 1700 році єпископом Яном Длужевським. Дзвін 1741 року був освячений єпископом Яном Ґнінським, тоді як найбільший, перетоплений у 1820 році за понтифікату єпископа Францішка Мацкевича, виготовлено з розбитого дзвона святого Михайла, фундованого у 1718 році єпископом Стефаном Рупнєвським. Решта три дзвони було перенесено сюди з костелу Матері Божої Переможної після ліквідації монастиря босих кармелітів.

Відомостей про первісну форму даху дзвіниці не збереглося; відомо лише, що він був укритий ґонтом. Сучасне покриття з бляхи походить із другої половини XIX століття і має форму низького шатрового даху, увінчаного металевим хрестом. З того ж часу походить і невелика прямокутна будівля, розташована біля вежі з боку церковного подвір’я. Її зведено на місці колишніх критих дерев’яних зовнішніх сходів, що вели на другий ярус. Сам вхід, попри те що нині закритий будівлею, зберігся до наших днів. У XIX столітті тут містився церковний склад, де зберігали катафалк та інше начиння. Перед Першою світовою війною приміщення виконувало функцію житла. Нині, після перебудови 1990-х років, об’єкт використовують сестри-урсулинки.