A település középkori templomának létét csak a pápai tizedjegyzékek bizonyítják: 1335-ben ugyanis említik a szihalmi templom plébánosát, aki nem fizetett tizedet. Bár az épület léte ez alapján nem kétséges, sajnos több adatunk nincs róla e korszakból. Ismert olyan elmélet is, miszerint a ma már nem létező, Szihalommal egykor szomszédos Csépes falu Szent Mihály tiszteletére szentelt temploma lett volna Szihalom temploma is, ezt azonban semmi sem bizonyítja. Az viszont biztos, hogy az 1670-es években már hallunk Szihalom plébánosáról; 1733-ban pedig a kőből épült romos templomot is említik. Ez valószínűleg a középkori eredetű, de a török időkben megrongálódott épület lehetett. A mai templom az 1750-es évek végén épült; arról azonban nem rendelkezünk egyértelmű információkkal, hogy a középkori helyén, esetleg annak alapjain, vagy más helyen, újonnan emelték.