Budowa Na głównego architekta został wyznaczony Carlo Rossi, który czuwał także m.in. nad projektem Budynku Sztabu Generalnego. Wybór miejsca w jakim zostanie wzniesiona rezydencja najmłodszego syna cesarza Pawła nie był od początku przesądzony. Brano pod uwagę np. teren przy placu Isaakijewskim (placu św. Izaaka), gdzie obecnie stoi Pałac MaryjskiWilk M., Od Petersburga do Leningradu, Warszawa 1980, s. 129.. Prace przygotowawcze rozpoczęły się w 1817 roku. W kwietniu 1819 r. powołano specjalną komisję mającą czuwać nad budową pałacu. Kamień węgielny położono uroczyście 14 lipca 1819 r., a budowa oficjalnie rozpoczęła się 26 lipca. Budynek został uroczyście otwarty 30 sierpnia 1825 roku. Budowa pałacu pochłonęła 7,6 milionów rubli.
Kompleks pałacowy thumb|250px|left|Pałac Michajłowski Architektura Carlo Rossi przemodelował całe otoczenie pałacu, przedłużając niektóre ulice i tworząc ich nowe odnogi. Tak by mimo odmienności w stylach, w sposób harmonijny wpasować nowy obiekt w dotychczasowe zabudowania, tworząc tzw. Plac Sztuk Pięknych. Zgodnie z zamierzeniami architekta Pałac Michajłowski jest doskonale widoczny z Newskiego Prospektu, łączy go z nim ulica Michajłowska. Przed nowym pałacem Rossi stworzył paradny dziedziniec ze skwerem, który od ulicy odgrodzony był metalowym parkanem.