Die ursprüngliche romanische Kirche stammte aus dem 11. Jahrhundert. 1226 erhielten sie die Angehörigen des Dominikanerordens und bereits in dieser Zeit wurde sie als altehrwürdig bezeichnet. Im 14. Jahrhundert wurde die Kirche – wahrscheinlich nach einem Brand – abgerissen und durch einen gotischen Bau ersetzt. In der hussitischen Zeit predigte hier Jan Hus, unter dem wachsamen Blick des ehemaligen Predigers der Clemenskirche Jan Protiva, der Hus beim Erzbischof denunzierte und sogar auf dem Konzil in Konstanz gegen ihn als Zeuge auftrat.
Die Clemenskirche war ein hussitisches Gotteshaus und gehörte bis 1621 der utraquistischen Kirche. Es wurde hier das Abendmahl in beiderlei Gestalt, das heißt mit Brot und Wein, gespendet. Nach den unheilvollen Ereignissen auf dem Weißen Berg fiel die Kirche an die Katholiken, die sie nutzten, bis sie 1784 im Rahmen der josephinischen Reformen entweiht und in einen Speicher umgewandelt wurde.
Seine Wiederauferstehung als Kirche erlebte das Gebäude erst 1850. Dank des Pfarrers Bedřich Vilém Košut wurde sie damals von der neu gegründeten evangelisch-reformierten Gemeinde erworben.
Die Kirche wurde mehrmals umgebaut, insbesondere Ende des 19. Jahrhunderts. Auf Anraten des Architekten Bohumír Kozák kam es in den siebziger Jahren des 20. Jahrhunderts zu einer gründlichen archäologischen Untersuchung, die den historischen Wert der Kirche offenlegte. Unter anderem wurden im Chorraum wertvolle vorreformatorische Fresken entdeckt und anschließend restauriert. Es handelt sich um gotische Engelsfresken und die Reste von Darstellungen zur Passionsgeschichte (interessant ist vor allem der Kopf Christi beim Einzug in Jerusalem). Kostbar ist auch eine Renaissancesteintafel von 1578. Die Botschaft ihres Textes hat durch die Jahrhunderte bis in die heutige Zeit nichts von ihrer Bedeutung verloren: „Das Wort des Herrn bleibt in Ewigkeit.“