A templom a korabeli Miskolctól különálló, a hajdani tapolcai apátság 10 holdas birtokán, az Avas ÉK-i oldalán elterült egykori Mindszent település plébániájához tartozott, és egy elbontott középkori eredetű kápolna helyén épült. 1728-ban Althán Mihály váci püspök és tapolcai apát kezdeményezésére kezdték építeni, barokk stílusban, melyet aztán utóda Máriássy Sándor fejeztetett be 1743-ban. Felszentelése 1744-ben történt Péter és Pál ünnepén, az ő nevükben. Az építés idejét és az építtetők neveit a főbejárat feletti kronosztikon örökítette meg, gazdag kőfaragványokkal, angyalokkal díszítve. A templom külső megjelenése akkor teljesen kialakult, a szobordíszekkel együtt, a tornyok kivételével. Az épületbelső azonban nem készült el erre az időre, az még több évtizeden át folyamatosan valósult meg. A főbejárati kapu és kripta bejárat, a belsőben az öt oltár és szószék készült el a felszentelésre, a festés, aranyozás, később készültek. A két sekrestye, felettük a két oratórium a szépen faragott bútorok és padsorok, a magas belső boltozatok különös ékei voltak már akkor a templomnak. Elkészült a templomudvar, kerítéssel, kapukkal. Megvalósult az orgona és az egy meglévő régebbi haranghoz még kettőt öntettek. Mindezek 1833-ig valósultak meg.
Jelentős állomás a templom történetében a királylátogatás, 1857-ben, amikor is Ferenc József a hatalmas templomot meglátta, felajánlotta az egyik torony felépítését, majd az egri érsek és a hívek adományaiból megépülhetett a másik torony is. 1864-ben kezdődtek az építkezések, és még abban az évben az egyik toronyra felkerülhetett az aranyozott kereszt, majd a következő évben a másik is elkészült, már eklektikus stílusban. Így lett a 19. század utolsó harmadában teljes a templom mai formája.
Az elmúlt kb.140 év alatt csak részleges javítások, felújítások készültek, melyek nem változtattak lényegesen az épület külső és belső megjelenésén. 1948-ban a háborúban aknarobbanástól megrongálódott egyik toronyablakot és környékét hozták rendbe, a toronysisakokat fedték át vörösréz lemezekkel, sajnos a két tornyon lévő nyolc óraszámlapot és az óraszerkezeteket megszüntették.
1949- ben a szentély belső felújítását végezték el, aranyozásokat, festéseket végeztek, a mennyezeti freskókat a mezőkövesdi Takács István ekkor festette. 1997-98-ban a tornyokon lévő két keresztet leemelték, aranyozását felújították, és a tartógerendáit kicserélték.