Neve a Maly névalakban 1234-ben tűnik fel.; a Miskolc nembeliek öröklött földje volt. 1332/37-ben Szent János tiszteletére szentelt egyháza és papja volt. 1544-ben felégették a törökök. 1576-ban református lelkész működött a faluban. 1685-ben nagyobb része elpusztult, 28 puszta ház mellett csak 8 volt lakott. Az 1732/33. évi plébánia összeírás ugyancsak elhagyott falunak mondja, a helyben maradt néhány lakosnak ekkor is református lelkipásztora van, de a régi katolikus templom romjai még láthatók, szentélye 1746-ban is fennáll. 1746-ban a 103 katolikus lélek mellett 137 a kálvinista személyek száma. Az 1768. évi egyházlátogatás idején a Szent Mihály tiszteletére épült, igen régi kőtemplom szentélye boltozat nélkül áll, a hajó fölött nincs tető. Az egyházközség ekkor Emőd filiája.

1774-ben a katolikus hívek megkezdték régi templomuk helyreállítását, de miután az új falakat kívülről tíz támpillérrel kellett megtámasztani, emiatt kissé befelé hajoltak. Az 1774. évi helyreállítás a híveknek, továbbá Bárány Jánosnak, a helybeli Aszalay-birtok akkor bérlőjének költségén történt. 1775-ben Bárány azt írja az egri püspökhöz, hogy „a szegény mályi templomocska szükségére az volt Páter Jesuiták (egri) Collegiumának tornácain levő oltárkákat örömest megvenném”. A helyreállított templomba a kisharangot az a görömbölyi egyház adta át ideiglenesen használatra, ahol ugyancsak Bárány volt a bérlő. A szentély és sekrestye a helyreállítás után is boltozott, a hajó mennyezetes, melyet 1822-ben javítottak. Egy oltár volt benne, Szent István király tiszteletére.

A plébánia visszaállítását 1805-ben királyi rendelet írta elő, de az első plébánost, Rózsa István minoritát csak 1813. november 1.-én vezették be. Filiák lettek: Kistokaj, Ládháza, Nyék faluk. Katolikus templom ekkor még egyik leányegyházban sem volt. 1804-ben a helyi lelkész a kántorház céljára épített egészségtelen szálláson lakott. Ekkor már a vallásalap volt a kegyúr, ez az 1816-ban kérelmezett templomépítést későbbre halasztotta.

Az 1840-es évek elejére rommá lett a templom, ezután a pap lakásán miséztek. 1845-ben az érsekség felterjesztésére a vallásalapból 10 600 Ft-t helyeztek kilátásba új templom építésére, továbbá a falu közepén lévő Aszalay-féle kétszintes vendégfogadónak paplakká leendő átalakítására. Miután az összeg egyik felét kiutalták, 1847 tavaszán Gantzberger Antal miskolci építőmester megkezdte a munkálatokat, év végéig a falakat félmagasságig felhúzta, de az 1848/49. évi események miatt az építkezés megakadt. Végre 1860-ban biztosították a költségeket, 1861 elején Streimmelwögel Mihály egri építőmester befejezte a templomépítést és a paplak átalakítását. A régi paplakot, templomot lebontották, kőanyagukat az új épületekbe építették be.

A klasszicista templom: műemlék jellegű, titulusa: Szent István király.

Forrás:

Soós Imre: 7. Mályi. In: Soós Imre: Az egri egyházmegyei plébániák történetének áttekintése. Bp., Szent István Társulat. 1985. 125. o.