Die erste Kastorkirche, bis Mitte des 13. Jahrhunderts vor den Toren der Stadt gelegene Kirche, wurde zwischen 817-836 unter Erzbischof Hetti von Trier mit Unterstützung Kaiser Ludwigs des Frommen in Koblenz erbaut und am 12. November 836 geweiht. Am Tage zuvor waren die Gebeine des hl. Kastors von Karden an der Mosel hierher gebracht worden. Wahrscheinlich wurde gleichzeitig das Stift gegründet und die Kirche zur Pfarrkirche erhoben. Geweiht wurde damals lediglich der Saalbau mit rechteckigem Chorabschluss, der aber bereits im 9. Jahrhundert um das heutige Querhaus mit halbkreisförmiger Apsis erweitert wurde. Das Stift St. Kastor wurde zum bedeutenden Treffpunkt und Versammlungsort der deutschen Kaiser und Könige. So wurden im Jahr 842 hier von den Gesandten der Söhne Ludwig des Frommen wichtige Vorbesprechungen geführt, die dann 843 im Vertrag von Verdun zur Teilung des Fränkischen Reiches in drei Teilreiche - Westfrankenreich, Lotharingien und Ostfrankenreich – führten. Im Juni 860 trafen sich Mitglieder der karolingischen Herrscherfamilie, um familieninterne Streitigkeiten zu schlichten.
In einer weiteren Bauphase wurde die Memoria vor dem Chor als kapellenartige Gruft über eine ringförmige Krypta mit der Kirche verbunden. Im 10. Jahrhundert wurde die Anlage im Osten um eine Chorrotunde erweitert. Vermutlich entstanden zur selben Zeit die beiden Seitenschiffe des Langhauses und der untere Teil des Westbaus (Eingangsbereich). Er wurde von den zwei Rundtürmen flankiert, die im 11. Jahrhundert von den heutigen, bis 1103 vollendeten Türmen ersetzt worden sind, sie waren allerdings erst fünf Etagen hoch.

Bis zum Reichsdeputationshauptschluss 1803 war St. Kastor ein Chorherrenstift mit Stiftsgebäuden vor der Westfassade und auf der Südseite, vor der sich auch der Kreuzgang befand, und einem am gelegenen Kirchhof für die Angehörigen der Pfarrei St. Kastor.
Nach der Aufhebung des Stifts (1802/1803) wurden die Stiftsgebäude und der romanische Torbau, der den westlichen der Kirche gelegenen Friedhof abschloss, abgebrochen. Unter der Leitung des preußischen Bauinspektors Johann Claudius von Lassaulx wurde 1830 mit einer völligen Innenrestaurierung begonnen. Ermöglicht wurde dies durch die finanzielle Unterstützung des Dechanten Edmund Bausch. Zwischen 1840 und 1860 wurde der Innenraum von Joseph Settegast mit Fresken versehen (bis auf das nicht mehr vorhandene Apsisgemälde). Die barocke Ausstattung (Hochaltar, Chorgestühl, Bänke) wurden damals größtenteils entfernt. Das endgültige Erscheinungsbild erhielt St. Kastor zwischen 1890 und 1894, als die gesamte Kirche durch Stadtbaumeister F.W. Maeckler mit einer Verblendung aus Tuffstein versehen wurde. Das rechte Seitenschiff und die südliche Sakristei wurden abgebrochen und mit geringerer Mauerstärke bzw. in reduzierter Breite wiederaufgebaut.
Am 6. November 1944 wurde St. Kastor bei einem englischen Bombenangriff beschädigt. Artillerietreffer im März 1945 beschädigten zusätzlich die Außenfassade. Die steinerne Substanz inklusive der Gewölbe blieb allerdings weitgehend intakt. Der Wiederaufbau begann 1948. 1955 erfolgte eine neue Ausmalung. Umfangreiche Sanierungs- und Restaurierungsarbeiten an den Türmen fanden in den Jahren 1979 bis 1990 statt. Große Teile der Tuffsteinverblendung und zahlreiche Werkstücke insbesondere der Freigeschosse wurden ausgewechselt. Der bis 1848/49 verputzte und farbig gefasste Außenbau blieb steinsichtig.
Papst Johannes Paul II. erhob am 16. Februar 1992 St. Kastor zur päpstlichen basilica minor.

Die außerordentliche Wirksamkeit des Baumeisters Johann Claudius von Lassaulx zu Anfang des 19. Jahrhunderts erfasste nicht nur den Kirchen-, sondern auch den Profanbau. Unverkennbar ist sein Baustil der Wiedergeburt gotischer und rheinisch-romanischer Bauformen auch an drei Profanbauten der Stadt Koblenz abzulesen. Sie stehen am Kastorhof und in der Rheinzollstraße.
Das Pfarrhaus von St. Kastor war nach den Plänen des Johann Claudius von Lassaulx 1829 fertiggestellt. Nach seinen Abrechnungsbüchern betrugen die Baukosten ganze 7.378 Taler. Die vorgelagerte „Freischwebetreppe“ gibt der schönen Gliederung der Frontansicht - vor allem im Oberstock mit seinen Blendbögen über den Rundfenstern und dem durchgehenden Sims, auf dem die Blendbögen aufsitzen - einen besonderen Akzent.