Коли саме церква стала костелом, думки дослідників розходяться. Польські вчені (С. Кардашевич, М. Орлович) вважають, що це сталося в 40-х роках XV ст. Причиною появи католицького храму в Острозі, на що погодилися князі Острозькі, було рішення Флорентійського собору (1439 р.) про унію східної і західної церков, а також привілей короля Владислава (1443 р.) про рівноправ’я православного і католицького віросповідань в Речі Посполитій.
В 1582 р., як твердить С. Кардашевич, зазгодою князя Костянтина-Василья Костянтиновича Острозького храм перетворено у парафіяльний костел. Інша версія про походження парафіяльного костелу в Острозі (А. Сендульський, Н. Петров, П. Батюшков) переконує в тому, що церква Пречистої Діви стала костелом лише на початку XVII cт. В тому ж столітті була збудована поруч з костелом плебанія. У 1621 р. в костелі встановлений великий вівтар, виготовлений львівськими різьбярами.
В 1625 р. з правого боку була прибудована каплиця Марії. У 1702 р. дах костелу перекритий гонтом заново, збудована нова дзвіниця. В наступному році почали будувати бабинець і притвор. В XVIII і XIX ст. костел неодноразово розбудовували і прикрашали пишними барочними вівтарями, які згадуються у візантійському описі храму 1805 р. В 1748-1753 рр. коштом Станіслава Яблоновського, який тоді був власником Острога, з лівого боку прибудували каплицю Яна Непомука – симетричну до каплиці Марії. Після цього храм набув у плані хрещатого характеру. Згодом кути між каплицями і пресвітерією заповнили невеличкими і низенькими об’ємами захристії і скарбниці. Таким чином, костьол, об’єми якого з чотирьох боків поступово збільшуються до центру і вгору, став пірамідальним. Над навою височіла баня з сигнатуркою.
Парафіяльний костел часто потерпав від пожеж у XIX cт, які нищили храм в 1809, 1848 і 4 червня 1889 років. Після останньої пожежі виникла необхідність будувати абсолютно новий храм. Його збудували на місці давнішого протягом 1897 р. за проектом архітектора В. Петровського в неокласицистичному стилі. В проекті була врахована умова, поставлена царською адміністрацією, яка дозволила будувати новий храм. Композиційно він повинен був відрізнятися від “попереднього барокового”. На відміну від старої будівлі, яка згоріла, новий костел має чітку хрещату композицію як у плані, так і в об’ємно-просторовому рішенні.