В 1814–1816 годах Грейг находился в Санкт?Петербурге. В это время он перешел в подданство России. Очевидно, этот шаг позволил поручить вице?адмиралу особую задачу: восстановить Черноморский флот, боеспособность которого заметно упала за последние годы. 2 марта 1816 года А.С. Грейга назначили главным командиром Черноморского флота и портов и военным губернатором Николаева и Севастополя.
В начале столетия флот не отвечал своему назначению. Вице?адмирал начал с научной организации дела. Он учредил при Черноморском адмиралтейском департаменте распорядительную часть, занимавшуюся перепиской, создал Артиллерийское управление, улучшил Депо карт, придав ему типографию и художников?граверов из числа моряков, ввел должности начальников отделений, усовершенствовал канцелярское дело и добился перевода архива Черноморского флота из столицы в Николаев, чем сократил переписку. В 1826 году флотоводец впервые в практике России создал штаб флота для организации боевой подготовки и разработки планов действия в военное время. Опираясь на организацию и подготовленных помощников, Грейг за несколько лет преобразовал все отрасли флота.
Вице?адмирал избрал в качестве базы судостроения Николаев. К 1832 году здесь на пяти верфях было 11 эллингов, из которых 9 соорудили при Грейге. На верфях была введена механизация. Не был забыт и Херсон, где заложили Спасское адмиралтейство, на котором с 1828 года по подряду строили корабли для Черноморского флота, в том числе линейные и фрегаты. В городе был основан литейный завод, отливавший необходимые детали для флота; на Херсонском канатном заводе также применили паровую машину, в Богоявленске парусная фабрика давала парусину высшего качества.
С 1818 года Грейг ходатайствовал о постройке в Севастополе сухих доков для ремонта кораблей, чтобы избежать килевания. Разрешение было получено в 1827 году, начались работы. Завершены они были уже при новом главном командире и потому получили наименование Лазаревского адмиралтейства. Новое адмиралтейство было создано в Измаиле, на реке Репиде — там строили суда Дунайской флотилии.
При Грейге было построено много малых судов, которые требовались для посыльной и крейсерской службы; они давали возможность молодым офицерам пройти школу самостоятельного командования. Моряк разработал проект канонерских лодок для Дунайской флотилии, предложил использовать на реке иолы.
Уже в 1820 году, через три года после появления первого парового судна на Балтике, в Николаеве построили пароход «Везувий» для портовой службы. В 1825 году был спущен в Николаеве первый в России военный пароход «Метеор», в 1826 году — пароход «Молния». Всего при Грейге были построены 5 и куплены 2 парохода.
По мере восстановления верфей появилась возможность строить линейные корабли и фрегаты. Грейг задумывал их с усиленной артиллерией, добиваясь высокого качества строительства, чтобы дорогие корабли могли служить эффективно и долго. Отказавшись от французских проектов с малой прочностью и остойчивостью, он предпочел использовать более совершенные английские образцы, предложил использовать созданный Ф. Чапманом и развитый А.С. Грейгом и К. Кнорре «параболический» метод проектирования. На основе этого метода, с применением диагональных креплений, были построены многие черноморские суда различных классов. В Николаеве построили первый на Черном море 120?пушечный корабль «Варшава», спроектированный Грейгом. Современники отмечали, что это было лучшее творение адмирала. В 1822 году в Херсоне был спущен первый в России 60?пушечный фрегат «Штандарт»; почти все последующие построенные при Грейге фрегаты — всего 7 — были того же класса. При недостатке средств на постройку кораблей фрегаты могли заменить их в линии и одновременно служить для крейсерской службы. Кроме того, строили транспорты для перевозки войск. Меры, принятые Грейгом, позволили резко увеличить численность судов. За время правления адмирала только Николаевское адмиралтейство выпустило 125 боевых судов (не считая портовых) — в шесть раз больше, чем за предшествующие 23 года своего существования.
Под руководством Грейга впервые в России была спроектирована морская паровая землечерпательная машина. Благодаря очистке ингульского и очаковского фарватеров можно было отказаться от камелей и отправлять корабли из Николаевского адмиралтейства с полным парусным вооружением своим ходом, так же как и возвращать обратно для ремонта.
Грейг не только увеличивал численность флота, но и добивался качества постройки, вносил многочисленные усовершенствования, увеличивавшие срок службы кораблей. Серьезное внимание он обращал на главное оружие кораблей — артиллерию. Зная, что пушки Луганского завода часто разрывает, он заказывал орудия на Олонецком заводе.
В 1825 году из 15 черноморских кораблей в строю были 10, тогда как на Балтике — всего 5, что свидетельствует о качестве кораблестроения. Немудрено, что когда вступивший на престол Николай I создал Комитет для образования флота, его членом стал вице?адмирал Грейг.