После этого Государь распорядился начать строительство нового дворца с церковью, посвященной архангелу Михаилу, и назвать дворец Михайловским замком. Его решено было возвести на участке, омываемом Фонтанкой и Мойкой, – там, где стоял обветшалый деревянный Летний дворец, построенный в 1746 году архитектором В. Растрелли для императрицы Елизаветы Петровны. Здесь в 1754 году и родился Павел I, рассказывают, что он впоследствии будто бы сказал: «Хочу умереть на том месте, где родился».
Именно при возведении этого дворца впервые и раскрылся талант В. Растрелли. Фасады широко раскинувшегося деревянного здания были украшены колоннами, пилястрами и декоративными скульптурами. Его парадные помещения образовывали восхитительную анфиладу, которая протянулась на десятки метров.
А первоначальная архитектура и украшения Михайловского замка принадлежали самому императору, о чем свидетельствуют карандашные наброски Павла I, хранившиеся когда-то в архиве Марии Федоровны. Михайловский замок мало походил на дворцовые сооружения Петербурга: в отличие от них он выглядит суровым, холодным и даже мрачно-замкнутым. Российский государь отталкивался от распространенной в европейских странах (в частности, в Германии) схемы построения прямоугольного в плане замка с прямоугольным же внутренним двором и круглыми угловыми башнями. Планы такого замка впоследствии обнаружили среди собственноручных чертежей Павла I.
Разработку проекта этого замка император поручил архитектору В.И. Баженову. Тому не пришлось разрабатывать новую композицию, так как она у него фактически была уже создана для Гатчинского дворца, задуманного им в виде квадратного каменного сооружения с внутренним двором восьмигранной формы. В.И. Баженов воспользовался своими прежними чертежами, а далекий от совершенства проект императора, видимо, вызвал у него ряд откровенных замечаний. Следствием этого и явилось отстранение его от должности руководителя строительных работ. Доработал баженовский проект и возглавил строительство Михайловского замка архитектор В. Бренна, строивший его под наблюдением «особой комиссии».
Искусствовед В.К. Шуйский в своей книге о творчестве В. Бренны тоже отмечает, что архитектор видел профессиональное несовершенство проекта Павла I и потому поставил перед собой задачу творчески переработать его. В. Бренна «разработал ансамбль, включив в него плац-парадную площадь, отдельно стоящие кордегарии, экзерциргауз (манеж) и конюшенный корпус. В соответствии с принципами романтизма дворец и площадь перед ним предполагалось окружить каналами, наполненными водой, с переброшенными через них подъемными мостами».