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

Парафіяльний костел часто терпів від пожеж в XIX cт. Вони нищили храм в 1809, 1848 і востаннє 4 червня 1889 року. Після останньої пожежі виникла необхідність будувати абсолютно новий храм, його створили на місці давнішого протягом одного 1897 року за проектом архітектора Віктора Петровського в неокласицистичному стилі.
В проекті була врахована умова, поставлена царською адміністрацією, яка дозволила будувати новий храм: композиційно він повинен був зовсім відрізнятися від "попереднього барокового”. На відміну від старої будівлі, яка згоріла, новий костел має чітку хрещату композицію як у плані, так і в об,ємно-просторовому рішенні.
Костел розташований в центральній частині м.Острога на вул. Князів Острозьких.