În Piaţa Victoriei, în faţa Palatului Victoria de astăzi, pe o parte a terenului fostului Han Niculcea, din sud-estul fostei grădini a lui N.Mavrogheni, a fost construit între 1898-1901 una dintre cele mai opulente clădiri din Bucureşti – Palatul Grigore Sturdza, realizat la comanda proprietarului, după planurile arhitectului Iulius Reinicke, elaborate în 1897. Sturdza a achiziţionat terenul de 937 mp de la municipalitate cu suma de 50 lei/mp. Imobilul nu a putut fi încadrat într-un stil arhitectural definit, suscitând în epocă o serie de aprecieri nu tocmai favorabile. Arhitectul Grigore Ionescu consideră că aceasta este „cea mai amestecată şi mai bizară construcţie din Bucureşti, pe ale cărei faţade - foarte întinse - îşi dau întâlnire, înfăţişându-se, elemente de epoci şi stiluri diferite, tăiate în materiale de tot soiul şi de toate culorile”. Proprietatea era delimitată de un gard monumental şi deţinea şi dependinţele: casa de administraţie, casa Catargiu, grajdul, fierăria, gheţăria, remiza, casa portarului sau chioşcul grădinarului.
Grigore Sturdza nu s-a bucurat de noul palat, stingându-se din viaţă în anul în care acesta a fost finalizat, iar moştenitorii l-au vândut statului, în anul 1904, cu suma de 500.000 lei aur. Astfel, palatul a devenit sediul Ministerului Afacerilor Străine pentru patru decenii.
În 1937 a început construirea unui nou palat al Ministerului de Externe, proiectat de arhitectul Duiliu Marcu, în imediata apropiere a Palatului Sturdza. Ulterior a fost elaborat şi un plan de sistematizare a zonei care punea în discuţie existenţa vechiului palat. Soarta acestuia a fost pecetluită de două dezastre: incendiul din 1942 şi bombardamentele din 23 august 1944, demolarea intervenind între 1945-1946.