Das alte Stuttgart hatte drei mittelalterliche Kirchen als Kristallisationspunkte seines Gefüges. Der Merian-Stich von 1634 zeigt im Bereich der „Eßlinger Vorstatt“ die „S. Leonharts Kirch“ noch eingefasst vom ummauerten Friedhof. Mit Turm, großer Uhr und mächtigem Dach in gleicher Höhe wie die Umfassungswände erscheint sie weitgehend im selben Umriss wie heute.
Außerhalb des alten ummauerten Kerns der Stadt hatten sich schon zu Beginn des 14. Jahrhunderts erste Häuser angesiedelt, zu denen um 1330 eine von den ,,Sant Lienhartz münch'' des bayerischen Klosters Fürstenfeld gegründete Kapelle kam. Die lose gewachsene Siedlung fasste wohl um 1393 Graf Eberhard der Milde zu einer geordneten Vorstadt zusammen. Vorbild für diesen Vorstadtmarkt war wahrscheinlich der Wenzelsplatz in der 1348/49 angelegten Prager Neustadt, wo sich Eberhard 1392 aus Anlass seiner Lehensbestätigung aufgehalten hatte.
Bald nach Anlage der Vorstadt entstand auch die Kirche, die in erster Linie als Friedhofskirche fungierte. Zwar wurden dort täglich, wie 1410 vermerkt, Messen gelesen, aber keine Pfarrgottesdienste abgehalten, da die Leonhardskirche nach wie vor der Stiftskirche untergeordnet war. Erst 1806 wurde die Kirche zu einer eigenständigen Pfarre.
Im Lauf der Zeit erhielt die Kirche eine Reihe von Pfründenstiftungen und 1511 stiftete Johannes Vestner, Kaplan an St. Leonhard, eine Prädikatur, auf die der Augustinereremit Dr. Johannes Mantel berufen wurde. Da keine Predigten Mantels erhalten sind, ist unklar, ob er dort im Sinne der reformatorischen Lehre, der er persönlich anhing, predigte.
1995 ging von St. Leonhard die Bewegung der Vesperkirchen aus. Auf Initiative der Pfarrer Martin Friz und Günter Renz steht die Kirche seither zwischen Januar und März mehrere Wochen für Obdachlose und Bedürftige offen. Neben warmen Mahlzeiten werden unter anderem eine human- und tiermedizinische Versorgung, Gesprächsmöglichkeiten und Berufsberatungen angeboten.
Am heutigen Chor der Leonhardskirche ist in den schmalen, zweibahnigen Fenstern eine strengere Formung als am Langhaus zu erkennen. Im Innern lag der Boden um mehr als einen Meter tiefer als heute und das Chordach war ursprünglich steiler. Der Chor und der im Verbund stehende Turm gehören der ersten Bauphase vor 1410 an; davor lag ein einschiffiges Langhaus, dessen Anschluss zum Chor noch im heutigen Dachraum erkennbar ist. Der Baumeister der Stadt war damals Hänslin Joerg, auf ihn dürften diese Bauteile zurückgehen.
Von 1463 bis 1466 wurde unter Aberlin Joerg, dem Sohn Hänslins, das einschiffige durch ein dreischiffiges Langhaus ersetzt. Auch die enge Netzrippenwölbung des Chors hat man damals ausgeführt sowie den Turm erhöht. Eine andere Werkstatt ergänzte Ende des Jahrhunderts die Alte Sakristei im Nordwinkel zwischen Chor und Langhaus. Der Bau hatte damit im Wesentlichen seine heutige Form: eine breit gelagerte spätgotische Hallenkirche in überschaubarer Proportion mit drei Schiffen zu fünf Jochen im Langhaus und einem einschiffigen, unmerklich breiteren Chor, dessen zwei im Gewölbe verschliffene Joche mit einem 5/8-Schluss enden. Kleine spätere Veränderungen am Bestand waren die neugotische Ergänzung des Ziergiebels über dem Westportal 1852 von Werkmeister Heimsch und der Anbau der Neuen Sakristei 1898 durch Theophil Frey.
Das heutige Äußere lässt die schweren Zerstörungen im Zweiten Weltkrieg kaum noch erkennen. Das moderne Maßwerk zweier Langhaus-Südfenster und die einfachen Fenster-Bogenfelder der Neuen Sakristei sind die einzigen Hinweise auf Ergänzungen der Nachkriegszeit. Ansonsten ist das nicht allzu große Langhaus ein charakteristisches Beispiel schwäbisch-württembergischer Hallenkirchen. Das Äußere ist schmucklos, Strebepfeiler mit geschweifter Verdachung und zweifachem Rücksprung über Wasserschlag gliedern die Wände entsprechend der einstigen Jochteilung im Innern, der untere liegt im Verlauf eines Horizontalgesimses, das den Gesamtbau in Höhe der Chor-Fensterbank umzieht und auch die Strebepfeiler umläuft. Es fällt auf, dass das erste Langhausjoch im Osten tiefer ist als die anschließenden. Dies mag sich daraus erklären, dass man während des Langhaus-Neubaus zunächst noch einen Rest des Altbaus zur Benutzung beibehielt, bis der neue angeschlossen werden konnte. Schwieriger zu erklären ist der Wechsel der Fenstergewände, die im ersten und zweiten Joch doppelt gekehlt sind wie in den Chorfenstern, während jene des dritten und vierten Jochs sowie der Westwand, ebenso der späteren Nordsakristei, nur eine einfache Kehlung haben.
Der die Kirche umgebende Friedhof wurde 1805 endgültig beseitigt. Neben einigen Grabsteinen am Chorpolygon erinnert daran vor allem die monumentale Kreuzgruppe außen vor dem Chor. Laut der Stiftungsurkunde von 1505 hatten sie „zu vergangener Zytt die erbern Jacob Walther genannt Kühorn der Elter selig und Clara Magerin wyland sin Eliche Hussfrouw vff dem kirchoff zu Sant Lienharten ain Stainin Krutz vffgericht“. Das originale Werk ist 1501 datiert, doch steht heute am Ort eine 1976 von Gustav Schönfeld angefertigte Kopie, die noch den Sockel des im Original verlorenen Golgatha-Hügels wiedergibt; die Originalfiguren sind heute im Chor der Hospitalkirche zu sehen. Meister der spätgotischen Gruppe, die zu den Hauptwerken ihrer Zeit gehört, ist Hans Seyfer (um 1465-1509) aus Heilbronn.
Das Kircheninnere ist stark geprägt von den Folgen der Kriegszerstörung. Am 25. Juli 1944 hat ein Luftangriff die Kirche schwer getroffen und nur ausgebrannte Außenmauern stehen lassen; alle Dächer und Gewölbe, auch die südliche Arkadenwand stürzten ein. Die Wiedernutzbarmachung unter Rudolf Lempp, eine der ersten nach dem Krieg, war durch äußerste Sparsamkeit gekennzeichnet, die Dachfirste wurden niedriger gelegt, um Holz zu sparen. An eine Wiederherstellung der Südarkaden oder der Langhauswölbung war nicht zu denken. Immerhin wurde im verhältnismäßig kleinen Chorraum das ursprüngliche Steingewölbe rekonstruiert, unter Einfügung erhaltener Schlusssteine. Bereits am 19. März 1950 konnte die Kirche wieder eingeweiht werden. Eine Renovierung 1982/83 nahm die gröbsten Einschränkungen der Nachkriegsreparatur zurück, darunter die bis dato störende Erhöhung des Chors mit knarrenden Dielen über der Heizungsanlage.
Den wiederhergestellten Chorraum beherrscht ein feinmaschiges Netzgewölbe. In den Ecken des Polygons sind die Gewölbedienste bis zum Boden geführt, was die Geschlossenheit des Raums verstärkt. Unter den wiederverwendeten Schlusssteinen erscheinen im Chorschluss die von Engeln gehaltenen Wappen links des Baumeisters Aberlin Jörg und rechts das seines Mitarbeiters Conrad von Gundelsheim. Der Choraltar wird heute von einem schmiedeeisernen Gitter aus dem späten 16. Jahrhundert eingefasst, das aus der Hospitalkirche stammt. Über dem Altar ist ein Kruzifixus aus der zweiten Hälfte des 17. Jahrhunderts angebracht. Nur ein kleiner, wohl um 1470 entstandener und aus Ditzingen stammender Altarschrein, eine Leihgabe des Landesmuseums Württemberg, erinnert heute an die einst vorhandenen mittelalterlichen Ausstattungsstücke. Der Altar, in seiner Gestaltung ein charakteristisches Werk des Stuttgarter Raumes, enthält zwei Apostel- und zwei weibliche Heiligengestalten, wovon jedoch nur eine – die heilige Margarethe – eindeutig identifizierbar ist.
Unter den im Chor angebrachten Grab- und Gedenksteinen sticht das Epitaph des aus Pforzheim stammenden Gelehrten Johannes Reuchlin (1455-1522) hervor. Es befand sich ursprünglich in der für das Dominikanerkloster erbauten Hospitalkirche, wurde nach dem Krieg aber an den Ort des tatsächlichen Begräbnisses versetzt, das Reuchlin nach dem Zerwürfnis mit den Dominikanern in der Leonhardskirche bestimmt hatte; es lag wohl vor dem östlichsten Langhauspfeiler der Nordseite. Die Aufschriften des Epitaphs in Hebräisch („ewiges Leben“), Griechisch („Auferstehung“) und Latein („im Jahr Christi 1501 hat sich und der Capnionischen [griech. ,Kleiner Rauch‘ = Reuchlin] Nachkommenschaft Johannes Reuchlin aus Pforzheim dieses Denkmal gesetzt“) weisen auf den Beginn der auch humanistisch geprägten Neuzeit. Weitere Denkmale erinnern an Familien der Stadt, so mehrere für die Familie Stickel, die zugleich prägnante Stuttgarter Beispiele für den künstlerischen Ausdruck an der Wende vom Manierismus zum Frühbarock darstellen.
Die Fenster des Chorschlusses erhielten 1957 Glasmalereien von Wolf-Dieter Kohler (1928-1985). Sie zeigen, typologisch einander zugeordnet, im Nordosten Szenen des Alten, im Südosten des Neuen Testaments und im Mittelfenster den Heiland innerhalb der Dreieinigkeit. Die West-Rose schmückt seit 1983 eine Glasmalerei von Adolf Valentin Saile (1905-1994), sie ordnet das Schöpfungswerk um den Sündenfall.
Das ehemalige Chorgestühl der Dominikaner, das nach dem Wiederaufbau in der Hospitalkirche keinen Platz mehr hatte, fand hier eine mehr museale Aufstellung. Die erhaltenen Teile wurden willkürlich zusammengestellt, der Block einer Sitzreihe steht heute an der Chornordwand, während sich der Hauptteil des Gestühls an der Langhaus-Südwand befindet. Die ursprüngliche Anordnung des Ensembles muss man sich U-förmig im Chor der ehemaligen Klosterkirche vorstellen, mit einer von Dorsale und Baldachin überragten hinteren Reihe und einer einfachen, um eine Stufe niedriger gestellten vorderen. Zwei Meisterinschriften dokumentieren verschiedene Herstellungs-Kampagnen: „1490 hat hannsz ernst von beblingen disz werck gmacht“ stand einst am Dorsale des Südteils und „1493 habend disz werck gmacht bruder conrad zolner vnd hans hasz“ an dem des Nordteils. Der Meister der Schreinerwerkstatt Hans Ernst war ein angesehener Mann, der auch für den Speyerer Dom arbeitete. Die von einem Spezialisten für Bildhauerwerke geschaffenen figürlichen Teile konnte Karl Halbauer auf den Meister der Sandsteinreliefs an der Kanzel der Waiblinger Michaelskirche beziehen. Demnach ist das Stuttgarter Gestühl „ein einmaliges Geschichts- und Kulturdokument [...] Auch als Kunstwerk besitzt es einen beachtlichen Rang“.