W związku z podjętą przez Radę Miejską uchwałą o mechanicznym oczyszczaniu miasta, w 1927 podjęto decyzję o wybudowaniu niezbędnego garażu mogącego pomieścić liczny tabor. Z braku właściwego terenu specjalnie na ten cel zakupiono plac przy ul. Madalińskiego 4 (późniejszy adres 10/14).
Głównym projektantem i zarazem kierownikiem budowy został Tadeusz Emmel, wszystkie prace budowlane wykonała wyłoniona w drodze przetargu firma „Zakłady Przemysłowo – Budowlane Bracia Horn i Rupiewicz S. A.” Fronton budynku, od strony planowanego przedłużenia ulicy Sandomierskiej ozdobiła płaskorzeźba Syreny autorstwa Zygmunta Otto oraz napis „Garaż Miejski”.
Halę o powierzchni 2432 metrów kwadratowych przewidziano na 60 – 70 samochodów; bezpośrednio przy niej wybudowano budynki warsztatów i magazynów. Wybudowano także dwa podziemne zbiorniki na benzynę o pojemności 25 000 litrów każdy oraz wagę wozową; budowa całego zespołu trwała 230 dni.
Obecnie:
w okresie powojennym podczas remontu usunięto zdobiący pierwotnie fasadę napis „Garaż Miejski”; rozebrano także budynek magazynowy od strony ulicy Melsztyńskiej. Po opuszczeniu zabudowań przez MPO, obiekt został przekazany na siedzibę Nowego Teatru Krzysztofa Warlikowskiego - adaptacja budynku została zrealizowana w latach 2014-2016.
