Костел Святої Анни був побудований з ініціативи князя Януша Острозького, який був власником Полонного. Януш Острозький перший з князів Острозьких прийняв католицтво в 1579 році.
Костел будувався 14 років, на фасаді є дата освячення костелу – 1607 рік. Перед будівництвом костьолу був спеціально насипаний невеликий пагорб. Однак цей костел проіснував недовго, в 1618 році його спалили турки. У 1646 році Краківський воєвода Станіслав Любомирський починає відновлення костелу, який був завершений в 1649 році. Костел був названий на честь Святої Анни. Вона була святою – покровителькою матері воєводи.
Поруч з костелом можно побачити залишки Полонської фортеці.
