Eine ältere „Lyskirche“ gab es sicher bereits in der ersten Hälfte des 10. Jh., eine erste vielleicht schon im 8. Jh. Es dürfte ein Grundherr namens Lisolf gewesen sein, der hier für sich und die auf seinem Gut abhängig Beschäftigten eine sogenannte Eigenkirche bauen ließ. Diese Art Kirchengründung ‚von privat‘ war ein noch bis ins 12. Jh. üblicher Vorgang. Aus der wohl bereits Maria geweihten ersten Kirche des Lisolf hat sich im Laufe der Zeit durch Namensumwandlung über „ecclesia Lisolvi“, „Lisolfikyrken“, „ecclesia de Lisolskirgen“ und ähnlichem die Bezeichnung „St. Maria in Lyskirchen“, also die „Marienkirche auf oder an der Stelle der Kirche des Lisolf“ gebildet.
Der heutige Bau wurde zwischen 1199/1200 bis etwa 1220 errichtet. Die kleine Krypta unter dem Chor dürfte wohl mehr als statischer Unterbau im beständig schlammigem Untergrund denn als Sakralraum gedient haben. In der Kölner Stadtsilhouette wäre St. Maria in Lyskirchen mit rheinseitiger Doppelturmfront das südliche Pendant zur im Norden gelegenen und etwas später begonnenen größeren Stiftskirche St. Kunibert geworden. Warum der zweite Turm Lyskirchens nie gebaut wurde, ist nicht bekannt.
Im Innern erhielt die Kirche den Belangen einer Pfarrkirche gemäß Emporen. So konnten möglichst viele Menschen dem Gottesdienst beiwohnen. Zwei der originalen dreiteiligen Emporenöffnungen sind noch zu Seiten der Orgelempore vorhanden. Architektonisch äußerst modern sind die hängenden Schlusssteine in den Seitenschiffen, die hier das erste Mal im Rheinland nachweisbar sind. Modernsten Tendenzen folgt auch das aus Frankreich stammende Travèensystem des Langhauses. Hier entspricht jeweils ein Joch der Seitenschiffe in der Länge einem Joch des Mittelschiffs, entgegen der üblichen kölnisch-rheinischen Verhältnisse von 2:1.
