Das gemütliche "Brezl Gwoelb entstand aus dem "Haus zu den vier Kronen" und vier kleinen, zwei- bis dreistöckigen Häusern.
Das erstmals 1241 erwähnte Gebäude stellte die Front des Hofes dar, der seinen Namen nach der Lederinnung führte. Sie hatte hier seit alter Zeit ihr Zunfthaus und ihre Herberge - das Gewerbe der "Lederer und Färber" war an das Wasser gebunden. Durch den heutigen "Tiefen Graben" - unweit vom Standort des heutigen "Brezl Gwölbs" floß zu früheren Zeiten der "Ottakringer Bach" bzw. der spätere "Alserbach".
Das Hauptgebäude - heute "Am Hof Nr. 11" - wurde 1881 zerstört und in den "Zwanzigern" neu erbaut. Von 1989 bis 1991 wurde dieses Haus mit viel Aufwand restauriert und dadurch in das "alte" Stadtbild eingefügt.
Das Haus in dem sich das "Brezl Gwölb" befindet, hat eine besondere Beschaffenheit: Es ist tiefer als hoch!
Das 1. Kellergeschoß, das jetzt ein Teil des Lokales ist, war zur Römerzeit ebenerdig - eine römische Mauer mit einer Fensteröffnung (links vom Stiegenaufgang) zeigt dies.
Die drei Kellergeschoße, die bis in dieses Jahrhundert noch mit fast allen Kellern im 1. Bezirk verbunden waren (man konnte z.B. von der Hofburg zum "Alten Rathaus" in der Wipplinger Straße "unterirdisch" gehen) wurden in den Kriegsjahren zugeschüttet und schließlich ganz zugemauert.
Bevor das "Brezl Gwölb" entstand, war hier eine Backstube - eine der ersten Bäckereien in Wien, welche die "Laugenbrezen" herstellte.
"Gwölb" als Altwiener Bezeichnung (Nestroy) für ein Lokal, hat hier eine doppelte Bedeutung, da es auch auf die Architektur zutrifft.