Как уже говорилось, М. С. Воронцов с детских лет любил водную стихию. В середине 1823 года на построенном в имении Мошна пароходе «Надежда» он плавал по Днепру, привлекая внимание многочисленных зевак. Это был первый пароход в здешних местах. В 1825 году «Надежда» была переправлена через днепровские пороги и прибыла в Херсон. Здесь ее стали использовать для буксировки барж в Николаев. А в 1827 году «Надежда» отправилась в первый рейс с пассажирами. На пароходе были комнаты для женщин — на четырех и для мужчин — на семерых.
Увлечение М. С. Воронцова морем способствовало его сближению с вице-адмиралом Алексеем Самуиловичем Грейгом. А во время Русско-турецкой войны 1828–1829 годов, при осаде крепости Варна, они стали товарищами по оружию.
А. С. Грейг был потомственным моряком. Его отец С. К. Грейг командовал отрядом в составе эскадры Г. И. Спиридонова в Чесменском бою (1777). В Русско-шведской войне (1788–1790) адмирал С. К. Грейг одержал победу в Гогландском сражении, сорвав планы шведов по завоеванию господства на Балтийском море и захвату Петербурга.
А. С. Грейг пошел по стопам отца. Во время Архипелагской экспедиции Д. Н. Сенявина он успешно командовал отрядом кораблей. В 1816 году вице-адмирал А. С. Грейг был назначен главным командиром Черноморского флота и портов и военным губернатором Николаева и Севастополя. С этого времени он стал жить в Николаеве.
С начала царствования Александра I флот в России находился в небрежении. Людские и материальные ресурсы предназначались в основном для сухопутного войска. На суше, а не на море, были одержаны важнейшие победы в войнах, в которых участвовала Россия с начала века по 1815 год. В беседе с А. С. Грейгом император признался, что он судит о флоте «как слепой о красках»1. В год назначения Грейга командиром Черноморского флота адмиралтейство в Николаеве было в том же виде, в каком оно существовало еще во времена Г. А. Потемкина-Таврического. Догнивали стапеля и другие строения. Суда давно отслужили положенный срок. Новые корабли не строились.
С приходом А. С. Грейга положение на Черноморском флоте резко изменилось. Благодаря его настойчивости была принята программа строительства пароходов, катеров, шлюпов и мелких судов, предназначенных для ведения разведки и перевозки грузов. В 1820 году в Николаеве был построен первый на Черноморском побережье России пароход «Везувий».
М. С. Воронцов мечтал о строительстве большого парохода для Одессы, который мог бы перевозить и грузы, и пассажиров. Своими мыслями он поделился с Грейгом: «Нужно устроить его таким образом, чтобы на нем были, подобно аглицким, хорошо обделанные каюты и помещения для двух или трех карет»2.
В 1828 году в Николаеве был построен пароход, который получил название «Одесса». Первый рейс он совершил из Одессы в Евпаторию.
Параллельно с гражданскими строились и военные корабли. В 1825 году был построен первый в России военный 14-пушечный пароход «Метеор», а в 1826 году — пароход «Молния». В мирное время эти пароходы использовались для буксировки плашкоутов с грузами. В дальнейшем было построено несколько 60-пушечных кораблей и 120-пушечный корабль «Варшава», а транспортные суда переделывались в бомбардирские, необходимые для штурма приморских крепостей.
В 1834 году в Англии был построен для Одессы пароход «Петр Великий». По прибытии в Одессу судно осмотрели М. С. Воронцов и вице-адмирал М. П. Лазарев, назначенный в 1833 году новым главным командиром Черноморского флота и портов и военным губернатором Николаева и Севастополя. Генерал-губернатор и вице-адмирал нашли конструкцию парохода отличной, а отделку всех частей прекрасной. В 1835 году на пароходах «Петр Великий» и «Наследник», построенный в Николаеве, начались регулярные пассажирские рейсы по Черному и Азовскому морям. А в 1836 году на пароходе «Петр Великий» и военном корвете «Ифигения» М. С. Воронцов совершил плавание вдоль восточных берегов Азовского и Черного морей.
В марте 1840 году в Аккерман приплыл построенный в Англии пароход «Граф Воронцов» и начал совершать рейсы между Аккерманом и Овидеополем, перевозя пассажиров и грузы. Эта линия обеспечивала сбыт соли, добываемой в озерах Бессарабии. И хотя рейсы были убыточными, Михаил Семенович считал, что убыток не может сравниться с пользой, доставленной краю пароходством. Он даже предложил заказать в Англии еще один пароход для этой линии, чтобы рейсы не прекращались во время ремонта парохода «Граф Воронцов».
В 1831 году в Петербурге был построен пароход «Нева». Обогнув всю Европу, он прибыл 4 марта в Одессу. 7 мая «Нева» отправилась в первый рейс, открыв линию между Одессой и Константинополем. В дальнейшем на этой линии плавали пароходы «Император Николай» и «Императрица Александра», построенные в Николаеве, и другие суда.