Фундамент Черноморского пассажирского флота был заложен строительством первого пассажирского парохода, получившего впоследствии имя «Одесса». Инициатором постройки стал генерал-фельдмаршал граф М. С. Воронцов, который в 1823 году был назначен генерал-губернатором Новороссийского края и наместником Бессараб"ской области. В 1826 году он писал об этом командиру Черноморского флота и портов вице-адмиралу А. С. Грейгу: «Пароход в Одессе устраивается для перевозки как тяжестей, так равно путешественников и их экипажей, а потому его устроить таким образом, чтобы в нем были, подобно аглицким, хорошо обделанные каюты и помещения для двух или трех карет».
В том же году был подписан контракт с херсонским купцом М. С. Варшавским на постройку парохода. Заложили судно в Николаеве. Строительство парохода обошлось в 235 тысяч рублей. Он мог перевозить 50 пассажиров и 200 тонн груза. Корпус парохода был деревянный, с медной обшивкой в подводной части. На нем стояли паровой котел и паровая машина мощностью в 70 лошадиных сил постройки завода Берда в Петербурге. Пароход предназначался для перевозки пассажиров и грузов между Одессой и портами Крыма.
Однако первенца пассажирского флота с самого начала преследовали неприятности. Когда пароход был построен, сразу выйти в Одессу он не смог. Ждали шкипера, механика и кочегаров, выписанных из Англии, однако к назначенному часу они так и не прибыли. В итоге, по ходатайству графа Воронцова, экипаж теплохода «Одесса» был укомплектован «мор"скими служителями», военными матросами.
В середине июля 1828 года судно наконец-то прибыло в Одесский порт. Воронцов письменно уведомил об этом капитана порта:
«Пароход, принадлежащий городу, прибыл и совершенно готов отправиться в Крым в первый рейс 22 июля сего года... Объявите, что пароход называется «Одесса», и что он будет отправляться в Крым еженедельно».
О прибытии парохода сообщалось и в «Одесском вестнике». Кроме этого, газета информировала: «...путешественники, желающие отправиться в Крым на теплоходе «Одесса», найдут в нем два отделения. Верхнее заключает в себе четыре комнаты с семью кроватями, две из оных назначаются предпочтительно для дам. За помещение в сем отделении для одной особы, с использованием зала для стола, для одной особы платится до Евпатории 40 рублей (ассигнациями), до Ялты — 60 рублей. Нижнее отделение состоит из 24 нишей, в которых могут поместиться 28 особ. Плата в нижнем отделении также с пользованием общею залою с особы — 25 рублей. Поселяне и рабочие люди будут платить только 10 рублей с человека, но они должны оставаться всегда на палубе».
В назначенный день, 22 июля 1828 года, пароход «Одесса» отправился в первый рейс, но сумел до"браться лишь до дачи графини Ланжерон: вышла из строя машина. Находившийся на борту судна для предоставления отчета чиновник А. Скальковский сообщал: «...обратно в порт Одессу пароход прибыл на парусах. По исправлении повреждения, вышел из Одессы 31 июля, но, пройдя Евпаторию, попал на группу скал близ Балаклавы и был спасен только благодаря присланному лоцману».
4 августа 1828 года теплоход «Одесса» прибыл в Ялту. Первое плавание выявило следующие недостатки: паровая машина для такого судна оказалась слабой, запас топлива (дрова) был явно недостаточным, палубная и машинная команда — слишком малочисленны. В августе пароход совершил еще один рейс в Ялту. Затем использовался для перевозки грузов между Одессой и Варной, где войсками командовал М. С. Воронцов. Напомним, что тогда шла русско-турецкая война.
В 1835 году «Одесса» завершила свое недолговечное плавание. Таким образом, пароход находился в строю лишь семь лет. Отремонтированная машина с этого судна была установлена на пароход «Митридат», построенный в Одессе в 1837 году.
