Серьезная структурная перестройка ожидала Морское ведомство. Уже через две с половиной недели после воцарения Николая Павловича был создан Комитет образования флота. Было известно, что в последнее десятилетие царствования Александра I флот находился в упадке. На Черноморском флоте вместо 15 кораблей и фрегатов по штату насчитывалось 10 судов. На Балтийском флоте из 27 линейных кораблей и 26 фрегатов оставалось 15 судов, а годных к плаванию — всего 5. Объяснялось это и передачей Англии эскадры Д. Н. Сенявина, блокированной в Лиссабоне в 1808 году во время русско-английского конфликта после Тильзита, и продажей части кораблей Франции и Испании, и последствиями наводнения 1824 года, повредившего ряд судов, и просто упадком кораблестроительной деятельности. В последние два года министерства маркиза И. И. Траверсе (1811–1828) корабли совершали маневры в основном в «Маркизовой луже» (часть Финского залива у Кронштадта).
В результате деятельности Комитета 1 сентября 1827 года было утверждено новое (предварительное) Положение о Морском министерстве с образованием вместо упраздненной Адмиралтейств-коллегии нового Адмиралтейств-совета под председательством морского министра, причем экспедиции были упразднены. На следующий год, 31 марта, для «сосредоточения» управления «в высшем отношении» был учрежден при Его Императорском Величестве Морской штаб, переименованный в 1831 году в Главный морской штаб. В связи с этим в 1828 году начальник старого штаба А. Ф. Моллер был переименован в морского министра (1828–1836). В конце 1831 года было изменено управление Черноморским флотом и портами. Командование сосредотачивалось в руках главного командира с правами и обязанностями командира отдельного корпуса. Начальником штаба Черноморского флота был назначен бесспорный авторитет для Николая Павловича в морской части М. П. Лазарев. Именно ему император доверял самые сложные ревизии, и по его докладу в 1836 году был уволен допустивший злоупотребления и воровство главный комендант Кронштадтского порта. Преобразования продолжались и позже. В 1832 году Морское ведомство вновь стало именоваться Морским министерством, но возглавлялось оно управляющим без прав министра. Главенствующая роль все больше переходила к Главному морскому штабу, а Морское министерство превращалось в хозяйственный департамент при нем. Раздельное существование двух органов имело и отрицательные последствия, поэтому в 1836 году снова вернулись к единой организации. По новому положению о Морском министерстве от 8 апреля 1836 года Морское министерство было полностью подчинено начальнику Главного морского штаба, получившего права министра. Одновременно А. Ф. Моллер был отстранен от должности, а управление министерством было возложено на начальника Главного морского штаба.
На протяжении четверти века управление флотом сначала фактически (с 1827 года), а затем и формально (с 1836-го по февраль 1855 года) находилось в руках весьма примечательной личности николаевского царствования — светлейшего князя Александра Сергеевича Меншикова (правнука А. Д. Меншикова). Из-за конфликта с А. А. Аракчеевым он в 1823 году был переведен из Военного министерства в Министерство иностранных дел, а на следующий год отправлен в отставку. В январе 1826 года повелением Николая I он был возвращен на службу и в 1827 году включен в состав Комитета образования флота. На следующий год он был назначен начальником Морского штаба (с 1831 года — Главного Морского штаба). В связи с новым назначением он получил звание контр-адмирала, а в 1833 году стал полным адмиралом. 30 сентября 1854 года А. С. Меншиков был переведен на должность главнокомандующего всеми сухопутными и морскими силами в Крыму, сохранив должность морского министра. Деятельность свою он закончил в 1855–1856 годах на посту кронштадтского генерал-губернатора.