De kerk van Noorddijk is om en nabij het jaar 1250 gesticht. Van het oorspronkelijk romano-gotische bouwwerk zijn alleen de zijmuren van het schip, gedeeltelijk althans, nog aanwezig. De kerk was toen kleiner, had de omvang van het tegenwoordige schip, met aan de oostkant een rechtgesloten koor of een absis (halfronde uitbouw). Verder waren de muren toentertijd hoger en eindigden ze in (meloen)gewelven.
Het koor en de toren zijn van latere datum. De vierzijdige koorruimte is in het midden van de zestiende eeuw tegen het schip aangebouwd. Een eeuw daarna verrees aan de westkant de huidige toren.
In de periode 1995-1997 is de Stefanuskerk ingrijpend gerestaureerd. Het karakter van die restauratie was conserverend: het negentiende-eeuwse kerkinterieur moest behouden blijven. Wel werd de bruikbaarheid van het gebouw door nieuwe voorzieningen, zoals centrale verwarming, een keukenblokje en een toilet verbeterd.
