Skupinu nemovitostí na nároží Karlova koliště (Koliště) a Hráze (tř. M. Horákové) získal v roce 1837 Libor Klein (1803–1848).
V roce 1843 zahájil přestavbu všech pěti starších objektů, které spojil do jediného pozdně klasicistního paláce s dlouhým dvoupatrovým průčelím (3+3+6+3+9) členěným pilastry. Úpravy prováděl stavitel Alois Rieder.
Už předtím byla součástí jednoho z pětice domů rozlehlá, vpředu pravidelně, vzadu romanticky upravená zahrada s centrálním pavilonem (původně zahrada prezidenta apelačního soudu Jana Křtitele Mitrovského, později proslulá Casino-garten Josefovského předměstí), ještě začátkem 50. let jedna z nejnavštěvovanějších brněnských zahrad.

Po smrti L. Kleina byla stavba paláce přerušena, dědičkou se stala dcera Adolfina, provd. von Pillersdorfová.
V 50. letech je už palác v majetku rodiny Hauptů. Od roku 1910 patřil Stephanu Hauptovi von Buchenrode, který v roce 1913 zahájil jeho další velkou přestavbu, projektovanou Leopoldem Bauerem.