Kirken var formentlig Københavns første kirke og den eneste, indtil opførelsen af Vor Frue Kirke i slutningen af 1100-tallet.
Muligvis stammer den ældste kirke på stedet fra 1000-årene. Den var oprindeligt bygget i træ og senere (måske omkring 1200) erstattet af en murstenskirke. Trækirken var ganske lang, måske ca. 10 meter i længden.
Måske blev stenkirken bygget på initiativ af biskop Absalon, da han overtog byen i 1160. Teglstenene kom til Danmark netop på det tidspunkt.
I begyndelsen af 1400-tallet blev kirken udvidet til dobbelt bredde og fik sideskib. Omkring reformationen i 1536 blev den revet ned, og der er ikke synlige spor af den længere.
Kirken lå ved den nuværende Frederiksberggade ud for nr. 25. Ved nedrivning af ejendommen Frederiksberggade 38 omkring 2008, fik arkæologerne mulighed for at finde spor af den ældste kirke. De fandt bl.a. en række begravelser på den kirkegård, der har været i forbindelse med kirken.
De nyeste udgravninger på Københavns Rådhusplads har dog vist, at der udenfor Vesterport har været en kirkegård, og dermed måske også en kirke – som kan være endnu ældre end Sankt Clemens.