Archeologický výzkum, který pod základy objevil část staršího pohřebiště, potvrdil, že stavba mohla vzniknout až někdy na počátku 12. století. Archeologové a stavební historici zároveň identifikovali dvě stavební fáze kostela bezprostředně připojeného k tehdy již stojící velké poutní bazilice sv. Václava. Zdá se, že zprvu se jednalo o poměrně nenáročnou stavbu s trámovým stropem, kterou v interiéru zdobily jen podřezané a vápnem přetřené spáry a jednoduché červené pruhy. V druhé polovině 12. století však došlo k přestavbě, během níž loď kostelíka získala klenbu. Hned poté byl interiér nejspíš omítnut a nově vymalován dodnes částečně dochovanými románskými malbami.

Kostel sv. Klimenta zjevně nikdy nebyl farní, a i proto o něm máme první zprávy až z roku 1417, kdy se objevuje v tzv. Erekčních knihách pražského arcibiskupství evidujících nově zřízené donace. Podle tohoto zápisu se kostelík pravidelně neužíval a ani se v něm nesloužily mše. Proto bylo rozhodnuto, že sem bude ze sousední baziliky přenesen oltář sv. Doroty a dalších světců. Pravděpodobný důvod tohoto rozhodnutí plyne také z Erekčních knih – v bazilice v té době vzniklo oltářů větší množství a patrně si jejich liturgický provoz překážel. Proto měl být jeden z nich přesunut do tehdy nevyužitého sousedního chrámu. Lze předpokládat, že vznik současné, dnes ovšem upravené oltářní menzy, souvisí právě s touto liturgickou úpravou. Kostel sv. Klimenta získal tehdy i svého stálého kněze, jímž se stal jakýsi Zulík ze Sobotky (nejspíš identický s boleslavským kanovníkem Petrem Zulkem).

V románském kostele sv. Klimenta na staroboleslavském hradišti se do dnešních dnů dochovala významná část originální nástěnné výmalby z poslední čtvrtiny 12. století, která umožňuje pokusit se o rekonstrukci původního stavu a zároveň si učinit představu o typických či standardních prvcích nástěnné výzdoby v tehdejších kostelech.

Kostel byl spolu s bazilikou sv. Václava v polovině 90. let minulého století prohlášen za Národní kulturní památku. Dnes se právem řadí mezi nejcennější evropské památky románské doby.

V roce 2021 proběhla obnova střechy a fasády kostela. Na fasádě byly obnoveny sluneční hodiny. Ty vznikly v roce 1840, jejich poslední oprava proběhla v roce 1925, nakonec z nich ale zbyla jen tyčka. V rámci opravy byly odkryty ve vrstvách omítek. Zaměřil je pan Miloš Nosek, který se slunečními hodinami zabývá již 30 let, podílel se na vzniku či obnově více než 150 hodin, navrhuje podobu hodin a pomáhá i při záchraně historických hodin u nás.