A templom eredetileg a XI. században, vélhetőleg az 1040-es években épült, centrális térelrendezéssel, bizánci mintára. 20×20 méteres, négyzet alaprajzú épületként kell elképzelnünk, minden oldalán félköríves apszis lépett ki a fal síkjából. Belül 4×4 pillérköteg osztotta 5 hajóra a teret. Ennek a templomnak már csak az alapfalai láthatók a föld felett, de altemploma épen maradt, látogatható, benne csodálatos, román kori freskókkal, Magyarország egyik páratlan jelentőségű műemlékévé emelve a feldebrői templomot.

A centrális templomot 150 évvel később, valamikor a XII.-XIII. század fordulóján alakíthatták keletelt, hosszházas, nyugati típusú templommá. Északi és déli falát elbontották, a déli és északi belső pillérsor közeit befalazták. A templom így keskenyebb lett, három hajónyi szélességű. A keleti végén továbbvezették a falakat, és íves záródású szentéllyel zárták le a teret. A szentély két oldalán, északon és délen kétszintes sekrestyeoratórium.

A templom titulusa a XIV. században Szent Kereszt-templom volt.

A templom déli oldalán látható gótikus ablakok a XV. századból valók. Ekkorra datálható a déli oldal bejárata is.

A XVIII. században többször felújították, átépítették a templomot. Ekkor készült el a ma is látható templomtorony a nyugati oldalon. A templomhajót csehboltozat, a szentélyt csehboltozat és félkupola fedi. Berendezése a XVIII.-XIX. századból való.

Műemléki helyreállítása 1870-ben az ép altemplom "felfedezése" után kezdődhetett meg, amely felfedezés Henszlmann Imre nevéhez köthető, majd a két világháború között, illetve 1975-1984 között folyt benne helyreállítási munkálat. A templom külső megjelenése ma jól mutatja a barokk (vakolt) illetve középkori (vakolatlan kő) falrészeket, számos építési periódusával, falképeivel, részleteivel fontos íratlan forrása az 1000 éves magyar állam történetének.