A templom, amely a remeteéletet a missziós munkával ötvöző pálos rend szellemiségét őrzi, középkori eredetű. Szent Egyed tiszteletére épült, valószínűleg a 13. század második felében, majd többször bővítették. 1434-ben titulusában már a Nagyboldogasszony neve is szerepelt. Toronyórájának egykori számlapja az 1501-es évszámot viseli.
A pálosok a Bocskai-felkelés idején, 1604 körül kénytelenek voltak elhagyni az újhelyi kolostort, így a templom pusztulásnak indult. Gótikus falai csak az északi oldalon maradtak meg teljes magasságban. A többit azután építették föl, hogy 1638-ban a pálosok visszatértek Újhelyre. A felújított templomot 1653-ben Kisdi Benedek egri püspök szentelte föl. 1660-ban Báthori Zsófia és fia, I. Rákóczi Ferenc itt tért át nyilvánosan katolikus hitre, és ezt követően ők építtették a Szent Kereszt mellékkápolnát. A Thököly-felkelés idején, az 1670-es években a kurucok többször megrohanták, felgyújtották vagy kifosztották. A zűrzavaros idők múltával, 1689-ban a Szent Kereszt kápolna kriptájában temették el Csepellényi György pálos misszionáriust, aki 1674-ben Egerfarmos mellett szenvedett vértanúságot.
A templom mennyezeti stukkói a 17. század végéről valók. A barokk főoltárt 1716 és 1721 között Johann Georg Strözius (Ströcius) lőcsei szobrász emelte, a Nagyboldogasszony és Remete Szent Pál tiszteletére szentelt mellékoltárokat pedig 1733/1734-ben Johann Güntzl eperjesi mester. A festett padsorokat (stallumok) Tatirek Félix pálos mester készítette 1717-ben. 1767-ben a Szent Kereszt kápolnában egy nagyméretű feszületet, valamint Szűz Mária, Keresztelő Szent János, Szent Anna és Szent Joachim szobrait helyezték el, amelyek a Jászón dolgozó Krauss János Antal művei. A kápolna freskója, amely Jézus üres sírjának felfedezését ábrázolja, 1770-ből való.
Miután II. József császár 1786-ben eltörölte a pálos rendet, az újhelyi kolostort és templomot a piaristák kapták meg. Sivulszky József piarista házfőnök 1804-ben a főoltárra helyezte a Szűz Mária mellékoltár képét, amelynek helyére Kalazanci Szent József képe került. Ettől kezdve a templom titulusa csupán Nagyboldogasszony volt.
A templom 1949 és 1993 között önálló plébániatemplomként működött, de csupán 1949 és 1953, valamint 1992 és 1993 között voltak piarista plébánosai. Legtovább, 1955-től Densz Géza egri egyházmegyés pap vezette, aki 1986-ban rablótámadás áldozata lett. Nagy érdeme, hogy az Országos Műemléki Felügyelőség 1968 és 1993 között elvégezte a templomnak és berendezésének teljes műemléki felújítását.
