Miał on stanąć na miejscu dawnego Pałacu Letniego, w którym nowy cesarz przyszedł na świat w roku 1757.
Z powstaniem zamku związana jest legenda, wedle której jednemu z żołnierzy stojących na warcie przy Pałacu Letnim miał się ukazać Archanioł Michał, polecić wyburzenie pałacu i wybudowanie w tym samym miejscu świątyni pod jego wezwaniem. Według innej legendy, gdy cesarzowa Maria Fiodorowna była w ostatnich dniach swojej dziesiątej ciąży, pewien nieznajomy człowiek miał powiedzieć Pawłowi, że urodzi mu się syn, któremu ma on nadać imię Michał oraz zbudować cerkiew pod wezwaniem Michała Archanioła. Syn, który wkrótce się urodził rzeczywiście otrzymał imię Michał.
Paweł, jeszcze gdy był wielkim księciem, miał też powiedzieć, że chciałby umrzeć w miejscu, w którym się urodził, co miało się spełnić. Nowa rezydencja miała ucieleśniać ideały rycerskie, w które Paweł głęboko wierzył. Zwłaszcza od 1798 roku, gdy został wielkim mistrzem katolickiego Zakonu MaltańskiegoHeller M., Historia Imperium Rosyjskiego, Warszawa 2009, s. 473.. Zamek Michajłowski miał zatem też symbolizować nową godność imperatora.