La 29 martie 1832, comisarul vopselei de rosu (departament administrativ al Bucurestilor in epoca) se adresa postelnicului Costache Grigore Sutu, avizand reluarea 'lucrarii zidului imprejmuirii gradinii ce ai inceput Dumneata a zidi acum'. Acesta va fi, simbolic vorbind, actul de botez al viitorului imobil, cunoscut sub denumirea de Palatul Sutu.
Anul 1833 a fost marcat in istoria proprietatii Sutu de hotararea marelui boier de a-si inalta case noi. Vechile cladiri nu mai corespundeau transformarilor sociale, economice si mentale din cel de-al patrulea deceniu al veacului trecut.
Arhitectii Johann Veit si Conrad Schwinck au fost insarcinati cu ridicarea marelui palat. Colaborarea dintre proprietari si constructori, nu lipsita de tensiuni si conflicte inclusiv juridice, s-a concretizat in anul 1834, prin finalizarea in linii mari a imobilului.
Construit in stil neogotic, cu patru turnulete poligonale, amplasate doua cate doua pe partile laterale, de nord si de sud, palatul Sutu se remarca prin spatialitatea unui interior, conferita de o cupola similara aceleia de pe conacul de la Golesti. Infrumusetarile aduse impunatorului edificiu au continuat insa. Astfel, in octombrie 1836, Costache Sutu comanda mesterului austriac Eser, executarea unui splendid policandru de alama, format din 24 de sfesnice, intocmai ca cel de la biserica Sf. loan Nou. Inspirata rezolvare a holului central, infaptuita in 1862, se datoreaza lui Karl Storck, recunoscut sculptor si artist decorator. Transformarile initiate de el constau in deschiderea a trei arcade, din crearea unei scari monumentale desfacuta in doua brate si din montarea in peretele din fata, a oglinzii adusa de la Murano si prinsa intr-un frumos ancadrament. Deasupra oglinzii se distinge si astazi, prin gingasia executiei artistice, medalionul sculptat in lemn al Irinei Sutu, sotia proprietarului.
A doua jumatate a veacului trecut, va reprezenta pentru Palatul Sutu, perioada de maxima stralucire. Grigore Sutu (1819-1893) si sotia sa Irina, fiica marelui bancher Stefan Hagi Moscu, s-au preocupat constant atat de edificiu cat si de parcul ce-1 incadra. Ei au adaugat cladirii marchiza sustinuta de piloni de fier, creandu-se astfel un elegant peron de intrare.
Impunatorul parc ce inconjura palatul se intindea pana spre fostul amplasament al bisericii Sf. Sava. In gradina puteau fi vazufi pelicani, fazani, pauni si un frumos bazin ce amintea -pastrand proportiile - de fantanile Palatului Versailles. Fastul de la palatul Sutu era de altfel recunoscut, admirat si invidiat de intreaga protipendada Bucuresteana.
Calator prin Bucurestii sfarsitului de veac, publicistul Italian Roberto Fava, retinea printre proprietatile particulare reprezentative din capitala, palatele Brancoveanu, Sutu, Ghica si Stirbey.
In primele trei decenii ale acestui secol, fosta ctitorie a postelnicului Costache Grigore Sutu primeste diferite destinatii, fapt care se repercuteaza negativ asupra edificiului si parcului adiacent. Concomitent, palatul va fi insa si martorul tacut al unor importante evenimente istorice.
In anii ocupatiei germane din primul razboi mondial, ctitoria Sutulestilor va deveni resedinta generalului Tülff von Tscheppe und Weidenbach, guvernatorul teritoriului ocupat. Aici, in actuala sala de conferinte a muzeului, guvernatorul va organiza un pranz de gala cu ocazia Anului Nou 1918. Cu acest prilej s-a purtat istorica discutie dintre feldmaresalul August von MacKensen si Alexandru Marghiloman in vederea incheierii cat mai grabnice a pacii dintre Romania si Puterile Centrale.
Zece ani mai tarziu, edificiul va deveni sediul Primariei Municipiului Bucuresti. Din cabinetul sau aflat in camera din dreapta salii mari cu balcon, a semnat Dem I. Dobrescu decizia de deschidere a primei expozitii permanente a Muzeului Municipal.
Sediu al Bancii Chrissovelony (1932), al Casei de Economii si Consemnatiuni (1942) si al Institutului de Constructii (1948), Palatul Sutu isi va redobandi, cel putin in parte, vechea infatisare cu prilejul operatiilor de restaurare intreprinse intre anii 1956-1958.
La 23 ianuarie 1959, in preziua aniversarii unui veac de la Unirea Principatelor, va fi inaugurat intr-o noua forma de organizare Muzeul de Istorie al Municipiului Bucuresti.
Palatul Sutu pare a-si fi regasit menirea fireasca. Ridicat din dragoste pentru frumos, el este astazi depozitarul unor valori inestimabile pentru trecutul Bucurestilor.