Der Bau des Katharinenhospitals war notwendig geworden, nachdem die Leibärzte Herzog Friedrich Eugens bereits im 18. Jahrhundert in einem Gutachten festgestellt hatten, dass die vorhandenen öffentlichen Gesundheitseinrichtungen – Seelhaus, Lazarett, Hospital (später Bürgerhospital) und Siechenhaus – zu klein und veraltet waren. Die Umbrüche und Kriege am Übergang vom 18. zum 19. Jahrhundert verhinderten jedoch, dass dem Gutachten Taten folgen konnten. Tragischerweise verhalf erst der plötzliche Tod von Königin Katharina dem aufgeschobenen Projekt zu neuer Aktualität.
Die beliebte Königin war am 9. Januar 1819 gestorben. Zum Andenken an sie schloss sich wenige Tage nach ihrem Tod ein Komitee zusammen, das der Caritas der Verstorbenen mit dem Bau eines neuen Krankenhauses gedenken wollte. Dafür kamen 45.000 Gulden von Privatspendern zusammen. Die Stadt Stuttgart gab ihrerseits 12.000 dazu und das Königshaus insgesamt 80.000 Gulden. Unter der Leitung von Nikolaus von Thouret erarbeitete eine von König Wilhelm I. eingesetzte Baukommission den Plan und feilte an der baulichen Umsetzung des neuen Krankenhauses. Am 24. Juni 1820 fand nach 14-monatiger Planung die Grundsteinlegung am unteren Kriegsberg statt. Zwischen 1820 und 1827 wurde das Katharinenhospital auf einem ca. 3,5 Hektar großen Gelände und H-förmigem Grundriss errichtet und am 9. Januar 1828 feierlich von König Wilhelm I. eröffnet. Patienten wurden in dem dreistöckigen Gebäude im linken, Patientinnen im rechten Flügel behandelt. Im Mittelbau befand sich neben der Gebärstation auch die Verwaltung. Medizinisch war das Katharinenhospital anfangs in eine Abteilung für „innerlich“ und eine für „äußerlich“ Kranke (Chirurgie) aufgeteilt.
Das Katharinenhospital war jedoch bald zu klein und musste im Laufe des 19. Jahrhunderts mehrfach erweitert und ergänzt werden. Der entscheidende Faktor hierbei war die starke Bevölkerungszunahme Stuttgarts zu dieser Zeit, denn zwischen 1820 und 1920 wuchs die Stuttgarter Bevölkerung um das 14-fache von ca. 22.000 auf über 300.000 an. Bis zum Ende des 19. Jahrhunderts entstand ein Komplex mit über zehn Gebäuden. 1869 wurde ein als Bau 2 bezeichnetes Gebäude, in dem bis 1938 die Hautklinik untergebracht war, eingeweiht. Die steigende Größe des Krankenhauses machte neben der Errichtung eines größeren Wirtschaftsgebäudes auch den Bau eines separaten Verwaltungsgebäudes sowie mehrerer Pavillons für Patientinnen und Patienten notwendig. Die letzte große bauliche Erweiterung vor Ausbruch des Ersten Weltkrieges war der Bau eines speziellen Operationsgebäudes im Jahr 1901. Insgesamt bot das Katharinenhospital zu dieser Zeit Platz für 720 Krankenbetten und war damit eines der größten Krankenhäuser Württembergs.
Als Konrad Röntgen 1895 die Entdeckung „einer besonderen Art von Strahlung“ öffentlich gemacht hatte, erkannte man in der Medizin bald das hohe Potenzial dieser Technologie für Diagnostik und Therapie. Auf Betreiben von Hermann Burckhardt, dem damaligen ärztlichen Direktor der Chirurgie, kaufte das Katharinenhospital bei Carl Schmid, einem Stuttgarter Hersteller medizinischer und chirurgischer Instrumente, am 7. Dezember 1896 das erste Röntgengerät. Damit war das Katharinenhospital, neben dem Universitätsklinikum Freiburg, eines der ersten Krankenhäuser in Süddeutschland, das diese Technologie anwenden konnte.
Während des Ersten Weltkriegs diente das Katharinenhospital als Militärkrankenhaus. Dabei wurden nicht nur die Räumlichkeiten des Hospitals für militärische Zwecke verwendet, sondern auch das Personal für solche eingesetzt. Leitende Ärzte waren teils in Feldlazaretten, andere an der Front tätig.
Auch während des Zweiten Weltkrieges war das Katharinenhospital zu großen Teilen militärischen Zwecken unterstellt. Zu dieser Zeit wurde die Kapazität des Hospitals auf über 1.000 Betten erweitert. Nach den ersten alliierten Luftangriffen auf Stuttgart im Jahr 1940 ergriff man umfangreiche Schutzmaßnahmen. So wurden die Kellerräume zu Schutzbunkern mit Krankenbetten ausgebaut und für medizinische Zwecke erweitert. Neben Bettenbunkern wurden auch Operationsräume geschaffen, die die Aufrechterhaltung der medizinischen Versorgung zu dieser Zeit gewährleisten sollten. All diese gefährlichen und schweren Arbeiten wurden von Kriegsgefangenen und Zwangsarbeitern ausgeführt.
Da nicht alle Patientinnen und Patienten in den provisorischen Krankenstationen unter der Erde Platz fanden, mussten außerhalb der Stadt Ausweichkrankenhäuser eingerichtet werden. Der überwiegende Teil der Patientinnen und Patienten des Katharinenhospitals wurde in die frühere Pflege- und Heilanstalt nach Stetten in das nahegelegene Remstal verlegt. Außerdem errichtete man auf dem Gelände des Hospitals zusätzliche Baracken.
Die Zeit des Nationalsozialismus schlug sich auch im Alltag des Katharinenhospitals nieder. Im Namen der Ideologie des „gesunden Volkskörpers“ wurden in Stuttgart an verschiedenen Krankenhäusern „eugenische Zwangssterilisationen und Schwangerschaftsabbrüche“ durchgeführt. Dazu gehörten das Krankenhaus Bad-Cannstatt, die Landeshebammenschule, das Karl-Olga-Krankenhaus, die städtische Frauenklinik und das Katharinenhospital. Zwischen 1934 und 1944 waren über 1.200 Personen davon betroffen. Das Katharinenhospital war dabei nicht nur ausführend tätig durch seine chirurgische Abteilung unter dem damaligen ärztlichen Direktor SS-Untersturmbannführer PD. Dr. Friedrich Gross und den Oberärzten Dr. Heinicke und Dr. Haedke, sondern auch maßgeblich an den Verfahren vor den sogenannten „Erbgesundheitsgerichten und Erbgesundheitsobergerichten“ beteiligt. Denn die ärztlichen Direktoren und Chefärzte weiterer Abteilungen und Kliniken des Katharinenhospitals – innere Abteilung, HNO-Klinik und Augenklinik – verfassten im Auftrag dieser Institutionen Gutachten über die nach dem „Gesetz zur Verhütung erbkranken Nachwuchses“ angezeigten Personen. Dabei beurteilten sie die Frauen und Männer als „erblich belastet“ und nahmen damit großen Einfluss auf die gerichtlichen Entscheidungen.
Am Ende des Zweiten Weltkrieges war das Katharinenhospital, wie viele andere Krankenhäuser Stuttgarts, vollkommen zerstört. Deshalb blieb die Nutzung der Ausweichkrankenhäuser und der vor Ort errichteten Provisorien auch für weitere Jahre notwendig.
Nach langen Debatten machte der Gemeinderat 1956 den Weg für einen Wiederaufbau des Katharinenhospitals am alten Standort am unteren Kriegsberg frei. Ein dafür in Auftrag gegebenes Gutachten war zuvor zu dem Ergebnis gekommen, dass dies für die Stadt und das Krankenhaus am günstigsten wäre. Nach einem Architektenwettbewerb, den die Architekten Richard Müller, Ludwig Eisenlohr Jr. und Otto Müller gewannen, begann 1957 der Wiederaufbau.
Die Bauarbeiten mussten mehrfach verlängert werden. Grund für die Verzögerungen waren einerseits bauliche Unwägbarkeiten, die zu Beginn noch nicht abzusehen waren. So sollte etwa auf die noch bestehende Bausubstanz der ehemaligen Hals-Nasen-Ohren-Klinik an der Seestraße Rücksicht genommen werden. Andererseits machte der medizinische Fortschritt entsprechende bauliche Anpassungen nötig. Unter anderem führte die sprunghafte Entwicklung der Strahlentherapie dazu, dass nachträglich ein spezieller „Strahlen-Bunker“ tief in die Erde gebaut werden musste.
Der Wiederaufbau teilte sich in mehrere Abschnitte auf: Die ersten im Jahr 1959 bezugsfertigen Gebäude waren die neue Hals-Nasen-Ohren-Klinik, die Klinik für Kiefer- und Gesichtschirurgie, die Augenklinik und die Apotheke. Drei Jahre später konnten die Medizinische Klinik II und die Chirurgische Klinik in Betrieb genommen werden, 1963 und 1965 der erste bzw. zweite Bauabschnitt der Medizinischen Klinik I. Den Abschluss des Wiederaufbaus bildeten die im April 1967 eröffnete Urologische Klinik, die im November 1967 eingeweihte Strahlenklinik samt erwähntem Strahlen-Bunker und Anfang 1968 die Blutzentrale sowie die Lehranstalt für medizinische technische Assistenten.
Am 19. Februar 1968 konnte Oberbürgermeister Arnulf Klett das neue Katharinenhospital einweihen. Dabei bezeichnete er die Einrichtung als „ein Hochleistungskrankenhaus […], das auf lange Sicht baulich wie funktionell und in seiner organisatorischen Struktur fortschrittlichen Geist dokumentiert“.
Im Zuge der in den 1990er Jahren beschlossenen, aber erst ab 2014 umgesetzten Standortkonzentration rückte das Katharinenhospital in den Mittelpunkt der Stuttgarter Gesundheitsversorgung. Neben dem Katharinenhospital wurden nämlich auch das Bürgerhospital, das Olgahospital und die Frauenklinik am Standort Mitte zusammengeführt. Auf Beschluss des Gemeinderates hin, wird das Katharinenhospital seit 2021 Stück für Stück neu gebaut.