«Последний, выстроенный при адмирале Грейге корабль, был трехдечный — „Варшава“; он построен по чертежу 120-пуш. английского корабля „Нептун“, но не имел его недостатков, над устранением которых Грейг сам трудился. Он дал „Варшаве“ параболическую подводную часть и большое водоизмещение, отчего корабль отлично ходил, был остойчив при самых неблагоприятных на море погодах и мог носить сильную артиллерию. Этот образцовый корабль общим мнением черноморцев признавался верхом познаний Грейга в корабельной архитектуре. До корабля „Варшава“ хотя и строились с такою подводною частью в Черноморском флоте военные суда, но они были не тех размеров. Трехдечных же кораблей в то время с подобными обводами ни у нас, ни в других флотах не существовало».
«Варшаву» спустили 6 ноября 1833 года, через месяц после отъезда адмирала в Санкт-Петербург. Качествами корабля восхищался уже преемник Грейга, М. П. Лазарев, которому довелось заниматься его вооружением. Отмечая, что корабль не уступит английскому, Лазарев писал о хорошей его остойчивости, управляемости и скорости, достигавшей 8 узлов:
«„Варшава“ ходит лучше всех кораблей… и смотрит во всех отношениях кораблем царским, каких на Балтике никогда не видывали, да и в Англии тоже…»
Уже в 1816–1817 годах был построен фрегат «Флора», первое на Черном море судно с диагональными креплениями по системе Сеппингса, значительно повышавшими прочность корпуса. Эту систему использовали и на последующих черноморских кораблях.
В 1822 году в Херсоне был спущен первый в России 60-пушечный фрегат «Штандарт»; почти все последующие построенные при Грейге фрегаты были того же ранга. Всего их выстроили семь. При недостатке средств на постройку кораблей фрегаты могли заменить их в линии и одновременно служить для крейсерской службы. Кроме того, их можно было строить быстрее, чем корабли. Современник Грейга писал:
«60-пушечные фрегаты „Тенедос“, „Эривань“ и „Архипелаг“ одинаковых размерений и чертежа заложены были в 1828 г., а в 1829 г. состояли уже в линии кораблей Черноморского флота; по величине своей и силе артиллерии мало в чем могли уступать 74-пушечным кораблям, каковы были тогда „Иоанн Златоуст“, „Пармен“ и „Пимен“, и поэтому во время турецкой войны 1828 и 1829 гг. именовались 60-пушечными кораблями».
Кроме того, строили транспорты для перевозки войск. Уже 29 июня 1817 года вице-адмирал рапортовал морскому министру:
«Сверх того, находящиеся здесь транспортные суда пришли в весьма худое положение, да и тех крайне недостаточно для предстоящих в них потребностей, и необходимо нужно поспешить постройкою потребного оных количеств».
Грейг предложил строить небольшие транспортные суда прибрежного плавания (тьялкшипы и бомшипы), в которых ощущался недостаток.
В составе флота не было бомбардирских кораблей для обстрела крепостей. По предложению Грейга в 1824 году такой корабль «Опыт» был перестроен из транспорта. Так как эксперимент оказался удачным, то при подготовке к русско-турецкой войне были перестроены из транспортов в бомбардирские корабли «Успех», «Соперник» и «Подобный».