Bereits im frühen 11. Jahrhundert wurde auf Drängen der hochadligen Emma aus dem Geschlecht der Immendinger die Hofgenossenschaft Stiepel mit einer kleinen Eigenkirche versehen. Heute ist die Erscheinung der Kirche geprägt durch den Umbau zur Hallenkirche um 1500; bei dieser Gelegenheit wurde ein zuvor außerhalb der Kirche liegender Brunnen, der das Ziel von Marienwallfahrten war, in das Nordseitenschiff der Kirche mit einbezogen. In der nördlichen Nebenapsis der Kirche befand sich bereits vor 1410 ein Marienaltar. Ziel der Wallfahrten waren eine nicht erhaltene Marienstatue, später auch eine Pietá.

Bei dem Gründungsbau handelte es sich um eine kleine Saalkirche mit einem eingezogenen Chor, die als auffälliges Ausstattungselement einen Fußboden aus rotbraunen und blaugrauen Tonplatten besaß.

Im 12. Jahrhundert wurde eine einjochige Gewölbebasilika mit ausladendem Querhaus errichtet, die sich durch ihren aufwändigen Dekor am Außenbau auszeichnet. Dieser setzte sich auch im Innenraum fort und korrespondierte mit einer umfangreichen Ausmalung, die die Bekanntheit und Bedeutung der Kirche in Stiepel begründet. Aus dem 12. Jahrhundert haben sich neben der Malerei über dem Triumphbogen mit segnendem Christus und Kain und Abel, auch die Personifikationen der Paradiesflüsse sowie die ältesten gemalten Ornamentteppiche in Westfalen in der Vierung erhalten. Die Darstellung des bethlehemitischen Kindermordes in der Nordapsis sowie die Flucht nach Ägypten an der Querhauswand stammen ebenfalls noch aus dieser Zeit.