Die ursprüngliche Marienkirche ist vielleicht aus der Kapelle eines angenommenen fränkischen Königshofes (heute Pfarrhaus von Liebfrauen) hervorgegangen, deren Estrich sich unter dem Chor der heutigen Kirche befand. Seit der Übetragung der entsprechenden Reliquien in den Jahren um 938-948 wurde die damalige Kirche allein dem hl. Florin geweiht. Um 1100 erfolgte ein Neubau der Kirche unter dem Stiftspropst Bruno, dem späteren Trierer Erzbischof Bruno von Lauffen. Es entstand eine romanische dreischiffige Kirche. Die damals flach gedeckte Pfeilerbasilika bezog im Osten teile der römisch-frönkischen Stadtmauer ein. Mitte des 14. Jahrhunderts (Schenkung 1350, Ablass 1357) wird die romanische Apsis der Kirche durch eine gotische ersetzt, 1582-1614 die Einwölbung des östlichen Langhauses durch Meister Dietrich, Ende des 16. und Anfang des 17. Jahrhunderts wird auch das Laeinschiff eingewölbt. Anfang des 17. Jahrhunderts werden die Glockentürme erneuert. 1671 erfolgte der Abbruch der Martinskapelle auf der Südseite der Kirche, um eine Straßenverbindung zwischen Florinsmarkt und Kornmarkt zu schaffen. Die bei der Beschießung der Stadt Koblenz im pfälzischen Erbfolgekrieg 1688 zerstörten Mittelschiffgewölbe wurden zwischen 1708 und 1711 erneuert. Um 1710 erhält die Kirche ein neues Südportal (wohl von Philipp Honorius Ravensteyn) mit der Figur des hl. Florin. Nachdem der südliche Turm 1791 durch Blitzschalg zerstört wurde, entschloss man sich, die neuen Turmhelme niedriger auszuführen. Nachdem 1794 französische Revolutionstruppen Koblenz besetzt hatten, wirde St. Florin als Magazin genutzt.
1803 wurde das Stift im Zuge der Umwälzungen der Franzosenherrschaft aufgehoben. Das Kircheninventar wurde zerstreut, das Schulhaus, die angrenzenden Stiftsgebäude und der Kreuzgang niedergelegt (1807-11). Die Kirche sollte 1807 sogar auf Veranlassung Napoleons zu einem städtischen Schlachthaus mit Verkaufsständen umfunktioniert werden. Doch dazu kam es nicht, da die Preußen 1815 das Regiment in Koblenz übernahmen. König Friedrich Wilhelm von Preußen übertrug das Gebäude im Jahr 1818 der evangelischen Militär- und Zivilgemeinde. 1820 wurde das Gotteshaus als evangelische Pfarrkirche geweiht. Die nach einem Brand 1791 aufgesetzten Turmhelme wurden bei der gründlichen Wiederherstellung der Kirche durch Hermann Cuno 1899 beseitigt und durch Spitzdächer ersetzt. In den Jahren 1929 und 1930 kam bei archäologischen Grabungen unter der gotischen Apsis (1350) das Fundament eines römischen Stadtmauerturms zutage. Die Dächer der dreischiffige Pfeilerbasilika wurde 1944 zerstört und 1951 wieder aufgebaut. 1970 erfolgte eine neue Ausmalung nach am Triumpfbogen gefundenen Resten der alten gotischen Bemalung. Barocke Blattgirlanden schmücken den ansonsten schlichten Innenraum der Kirche. Im Gewölbe des Nordturms stehen zwei fränkische Steinsärge, die 1929 bei Ausgrabungen im Kirchengarten gefunden wurden. Im Deckengewölbe der Taufkapelle ist eine Kanonenkugel angebracht. Sie soll an die Beschießung der Kirche durch die Franzosen 1688 erinnern.