První zmínka o kostele pochází z roku 1291. Tehdy patřilo patronátní právo premonstrátskému klášteru v Doksanech (až do roku 1849). V roce 1426 byla Horní Police dobita husity a kostel zničen. V roce 1523 byla na břehu Ploučnice nalezena soška Panny Marie. Dle tradujícího vyprávění ji zbožné ruce vytáhly z vody a darovaly zdejšímu kostelíku. Od této doby se traduje vznik poutního místa. Soška byla brána jako nebeský dar a lidé se jí přicházeli poklonit. V roce 1682 byl zaznamenán takový příchod poutníků (na 4000 lidí), že se farář Michael Gabriel Jantsch obrátil s hejtmanem panství Janem Jiřím Hertychem na majitele a patrona kostela Julia Františka, vévodu Sasko – Lauenburského, aby nechal kostel rozšířit. Této žádosti vyhověl a povolal k sobě litoměřického stavitele Julia Broggia, který v roce 1688 začal se stavbou nového kostela. Starý kostelík byl téměř celý zbořen a na jeho místě postaven větší. Je to vlastně střední část nynějšího kostela, kterou tvoří střední loď s přilehlou věží. V roce 1689 převzala panství po Juliu Františkovi jeho dcera Anna Marie Františka, která po něm stavbu kostela dokončila. Brzy se ukázalo, že nový kostel se stal opět nedostatečným, a tak Anna Marie rozhodla o jeho dalším rozšířením.

Nová stavba začala v roce 1717. K nově postavenému kostelu se přistavovaly obě postranní lodi, zbudovány empory a přistaven chór a sakristie. V roce 1722 byla ještě nová volně u vchodu stojící zvonice a v následujících letech křížová cesta a fara. To vše bylo hotové v roce 1725. V roce 1723 byla zřízena zadní budova pro čtyři kaplany, tzv. kaplanka a v roce 1725 byl mezi farou a kaplankou zřízen spojovací trakt.
Nejen v oktávu svátku Navštívení Panny Marie, ale i v ostatních mariánských svátcích sem putovalo mnoho poutníků. Proto se velkovévodkyně rozhodla zdejší faru povýšit na arciděkanství, založila nadaci pro jednoho arciděkana a čtyři kaplany. Tento výnos schválil 10.září 1723 litoměřický biskup Jan Adam hrabě Vratislav z Mitrovic a byl zanesen do zemských desek 22. listopadu 1723.
Anna Marie Františka stále usilovala o zvýšení lesku a prestiže poutního místa. Na její žádost udělil papež Klement XII: 6.července 1736 arciděkanu v Polici práva používat pantifikálie ad instar abbarum, tzn. právo nosit při slavnostní mši sv. biskupskou mitru a pedum (berlu) a mši svatou odsloužit jako biskup (dnes je titul arciděkanství spojeno jen s poutním místem a právo nosit berlu a mitru už bylo zrušeno). Pro povznesení velkovévodkyně darovala dvě těla svatých, tělo mučednice sv. Kristiny získala od papeže Innocence XIII. dne 3. června 1722 a tělo mučedníka sv. Pavla od papeže Alexandra VII. dne 10. ledna 1727.
V roce 1861 nechal majitel panství císař Ferdinand provést renovaci kostela s čímž se započalo ve středu 3.dubna. Byla položena nová střecha, proběhla oprava zdiva kostela a věže. Do presbytáře a střední lodi kostela byly dány nové dlažební desky...
Poslední úprava střech kostela i křížové cesty, jakož i zdiva začal provádět, z důvodu poničení od bomb na konci války roku 1945, poslední správce arciděkanství Mons. Josef Stejskal za pomoci několika dobrovolníků z řad věřících. Mons. Josef Stejskal byl 15. a zároveň nejdéle slouužícím arciděkanem v Horní Polici. Odsloužil zde na den přesně 60 let.
Vrcholnou návštěvnost lze vidět v údobí let 1730 – 1760. Některé prameny dokonce uvádí, že Mariánská Police byla vedle Bohosudova nejvíce navštíveným poutním místem v severních Čechách.