Der Vorgängerbau des heutigen Gebäudes war 1893 nach Abbruch von klassizistischen Häusern aus dem frühen 19. Jahrhundert errichtet worden. Der zwischen Königstraße, Bolzstraße und Stauffenbergstraße (der damaligenTheaterstraße) gelegene Königin-Olga-Bau hatte seinen Namen nach der aus dem Hause Romanow stammenden Königin Olga (1822-1892) erhalten, der Ehefrau des Königs Karl I. von Württemberg und Vorbesitzerin des Grundstücks. Nach ihrem Tod ließ ihre Erbin Herzogin Wera von Württemberg (1854-1912), die zugleich eine Großfürstin von Russland war, nach einem Entwurf der Architekten Lambert & Stahl einen großstädtischen viergeschossigen Komplex errichten. Dieser vereinte verschiedene Funktionen und repräsentierte auf der Bedeutungsebene ein Abbild der Übergangszeit von der Residenz zur modernen Großstadt. Denn der Bau war beides, ein zeitgemäßes Geschäftshaus und ein in Palastform gestalteter Bau, der die am Schlossplatz noch immer deutliche Präsenz der Monarchie darstellte, sowohl durch die Bauherrin als auch durch die Formen der Architektur.
Eine Sockelzone mit Läden und Schaufenstern war in Arkadenform mit Rundbogenfenstern im Mezzaningeschoss gestaltet. Darüber erhoben sich bis zum Traufgesims die beiden Hauptgeschosse, in denen anfangs unter anderem ein Offizierscasino und ein Adelsclub untergebracht waren. Die Front zum Schlossplatz war in der Art eines barocken Palastes gegliedert, mit Pilastern zwischen den Fenstern und über dem Hauptportal einem leicht vortretenden Mittelrisalit, der nach oben von einem Giebeldreieck mit dem Wappen der Herzogin seinen Abschluss fand. Bezeichnend für den noblen Standort war die abgestufte Gestaltung der Gebäudeecken: Zur Königstraße bürgerlich mit Lukarnen-Bekrönung, an der dem königlichen Neuen Schloss gegenüberliegenden Ecke jedoch deutlich aufwendiger mit massiver Rotunde unter einer Kuppel mit Laterne. Nach Südosten schloss sich – unter dem gemeinsamen Mansarddach als selbstständiges Bauteil gestaltet in ruhigeren Formen und ohne Pilaster – ein Stadtpalais an, das der Herzogin Wera als Witwensitz diente.
Nach ihrem Tod ging das ganze Gebäude 1917 in den Besitz der Darmstädter- und Nationalbank (Danatbank) über, die hier ihre Stuttgarter Filiale unterbrachte. Der 1931 erfolgte Zusammenbruch dieser Bank im Zuge der Weltwirtschaftskrise zog den Verkauf an die Dresdner Bank nach sich. Die Bank nutzte den Bau oben für ihre Geschäftsräume, im Erdgeschoss befand sich die Schalterhalle. Die Jahre 1944/45 brachten sowohl für den Bau als auch für die Bank das vorläufige Ende. Nachdem das Gebäude im Luftkrieg ausbrannte und nur noch die Außenmauern standen, wurde 1945 die Dresdner Bank ebenso wie die anderen Großbanken wegen ihrer Beteiligung an NS-Verbrechen durch die Alliierten aufgelöst. In der amerikanischen Besatzungszone gingen ihre Filialen in einer unter der Aufsicht der Besatzungsmacht neu gegründeten Allgemeinen Bankgesellschaft (Allbank) auf. Diese übernahm auch das Grundstück und begann im Frühjahr 1948 mit Planungen eines neuen Gebäudes unter Verwendung der Fundamente und Grundmauern.
Die prominente Lage am zentralen Platz der Stuttgarter Innenstadt rückte das Projekt in den Fokus der Auseinandersetzungen um die Frage, welche Richtung der Wiederaufbau nehmen sollte: entweder unter Berücksichtigung der Bautradition und im Sinne der angesehenen, allerdings durch die Mitarbeit im „Dritten Reich“ im Ruf geschädigten Stuttgarter Schule der Architektur, oder im Sinne der Architekturmoderne, die nach 1945 in den zuständigen städtischen Behörden – der von Walter Hoss (1900-1993) geleiteten Zentrale für den Aufbau Stuttgarts (ZAS), dem Stadtplanungs- und dem Baurechtsamt – die Oberhand hatte. So war an dieser Stelle an eine für Stuttgart maßgebliche Weichenstellung gedacht, die auf eine unmissverständlich moderne Architektur hinauslief und auch die zerstörten bzw. beschädigten Bauten am Schlossplatz, darunter auch das Neue Schloss aus dem 18. Jahrhundert und das 1912 errichtete Kunstgebäude des Architekten Theodor Fischer (1862-1937), betreffen würde. Dagegen stand Hans Huthsteiner (1884-1951), Direktor der Allbank und Anhänger der Bautradition. Unter den potenziellen Bauherren am Platz war seine Bank nicht nur der einzige private Akteur, sie war auch eher baufähig als die anderen, d.h. man verfügte sofort nach der Währungsreform über die notwendigen Mittel.
Im Auftrag der Bank entwarf der Architekt Otto Linder (1891-1976) – ab Herbst 1948 in Arbeitsgemeinschaft mit Erich Hengerer – ein Wiederaufbauprojekt, das Teile der Ruine einbezog und bei übernommener Stützenstellung durch niedrigere Raumhöhen ein zusätzliches Geschoss gewann. Über einer vereinfachten Fassade, wiederum mit aufgehenden Pilastern oberhalb der Sockelzone, war ein Walmdach vorgesehen. Es war keine Überraschung, dass zwei nacheinander vorgelegte Entwürfe von Linder und Hengerer keine behördliche Zustimmung fanden. Zugleich erging die Empfehlung für ein flaches Dach wie in der Architekturmoderne üblich, womit die Erwartung verbunden war, dass etwas anderes als ein moderner Entwurf dann kaum möglich schien.
Huthsteiner suchte nun Hilfe bei Paul Schmitthenner (1884-1972), der als Berater hinzugezogen wurde, und riskierte damit den nächsten Konflikt, denn einem Entwurf des prominenten früheren Architekturlehrers der Stuttgarter Schule war die Ablehnung beinahe sicher. Im November 1949 lieferte Schmitthenner einen ersten Entwurf mit flachem Dach, jedoch in abstrahiert traditionellen Formen, der sogleich als Bauantrag eingereicht wurde. Der Hauptbaukörper mit glatter Natursteinfassade war horizontal zweigeteilt; über dem dritten Geschoss erhoben sich leicht auskragend zwei weitere, durch Pilaster gegliedert. Darüber folgte zurückgesetzt hinter einer umlaufenden Terrasse ein zweigeschossiger flachgedeckter Dachpavillon, bei dem sich die Pilaster fortsetzten.
Um Schmitthenner und den Bauherrn zu stoppen, wurde nun schweres Geschütz aufgefahren. Die Presse brachte ein die monumentalen Züge des Projekts betonendes Modellfoto, vor der Wiederholung von NS-Architektur wurde gewarnt. Richard Döcker (1894-1968), der Kontrahent Schmitthenners im nach 1945 erbittert geführten Streit um die Neuausrichtung der Stuttgarter Schule an der TH, führte in seiner stark beachteten Antrittsvorlesung im Januar 1950 den Entwurf als Negativbeispiel vor, das einer überwundenen Epoche angehöre. Auch Paul Bonatz (1877-1956), wie Schmitthenner ein Exponent der früheren Stuttgarter Schule, schaltete sich aus dem Exil in der Türkei in die für den Wiederaufbau Stuttgarts konstitutive Debatte ein, die Marc Hirschfell im Detail nachgezeichnet hat. Bonatz forderte ein mit Rücksicht auf die Nachbarschaft niedrigeres Gebäude ohne Dachpavillon und fand dafür viel Zustimmung. Einerseits war nun klar, dass nur ein revidierter Entwurf genehmigt würde, andererseits galt Schmitthenner als Autorität, dem selbst sein einstiger Schüler Walter Hoss einen gewissen Respekt nicht verwehrte.
Schließlich zog das Aufsicht führende württembergische Innenministerium die Entscheidung an sich und genehmigte im April 1950 das vorgesehene Volumen, jedoch mit nur eingeschossigem Aufbau. Für die Ausführung des ersten Bauabschnitts an der Bolz- und Stauffenbergstraße (1950/51) lieferte Schmitthenner einen nochmals modifizierten Entwurf, der die Lehren aus dem Streit zog und die Wuchtigkeit des ersten Projekts vermied, in dem die Aufteilung in Sockelzone und Obergeschosse in den Maßen des Vorgängerbaus übernommen wurde. Die kopflastige Schwere des zuvor auskragenden Bauteils war damit ebenso vom Tisch wie die Pilaster, die bis dahin stark hervorgehobene Eingangszone wurde stark abgespeckt. Umstritten blieb die mit einer siebenbogigen Arkade versehene, ein Stück vor die Bauflucht geschobene Nordwestfassade des zweiten Bauabschnitts (1953/54), welche den Schlossplatz und die Königstraße als jeweils eigene abgeschlossene Räume akzentuiert. Die an dieser Stelle bewusst gesetzte leichte Verengung steht für die von Schmitthenner praktizierte Auffassung von gefassten Räumen in der Stadt, während Richard Döcker und Willy Hoss den Wiederaufbau nutzen wollten, um die damals aktuelle Doktrin des „fließenden Raumes“ durchzusetzen.
Der Königin-Olga-Bau war das erste fertiggestellte Gebäude am Schlossplatz, während die Bauten ringsum noch in Trümmern lagen. Er funktionierte gewissermaßen als Leitbau für die Wiederherstellung des Neuen Schlosses und des Kunstgebäudes, denen noch Mitte der 1950er Jahre der Abbruch zugunsten eines radikal modernen Aufbaus drohte. Seit 1955 residierte hier die nach dem Ende des Besatzungsstatuts wieder zugelassene Dresdner Bank AG, bis sie 2009 von der Commerzbank übernommen wurde. Der Königin-Olga-Bau war 2004 durch die Württembergische Lebensversicherung AG erworben worden, die es nach der Auflösung der Bank im Inneren als repräsentatives Bürohaus mit Gastronomie im Erdgeschoss umgestaltete. Das Gebäude steht unter Denkmalschutz.