Менее чем через пять лет после того как Хаджибей был отвоёван у турок, 2 сентября 1794 г. началось строительство порта и нового города. Императорский рескрипт был подписан за три месяца до того, 27 мая 1794 г.

Уже в начале 1795 г. город был переименован и назван Одессой в честь древнегреческого поселения Одесосс, предположительно находившегося неподалёку, на левом берегу Тилигульского лимана (как выяснилось впоследствии, на самом деле в Болгарии), продолжив традицию называть новые города на греческий манер.

Легенда гласит, что на балу, в присутствии императрицы зашёл разговор о новом черноморском порте и крепости Хаджибее, недавно отвоёванном у турок. Некто из придворных предложил переименовать Хаджибей и напомнил о древнегреческой колонии Одессос. И вот тогда Екатерина якобы повелела: «Пусть же Гаджибей носит это эллинское название, но в женском роде.»

Новое название города Одесса впервые встречается 10 января 1795 г. Однако народ упорно называл Одессу Хаджибеем. Дошло до того, что стражники на въезде в город спрашивали каждого, куда они едут. Если отвечали: «В Одессу», то пропускали. Тех же, кто говорил «В Хаджибей», пороли. Похоже, это помогло: телесные наказания давно отменены, а Одессу никто не называет Хаджибеем…

В 1797-1802 гг. Одесса входила в состав Новороссийской губернии, а в 1805 году стала центром Новороссийского края, которым и была до 1874 г.

Строилась и развивалась Одесса быстро. В 1795 г. учреждены магистрат, таможня и карантин. Произведена закладка церквей Св. Николая по проекту архитектора фон Резанта (на месте современного Кафедрального Преображенского собора) и Св. Екатерины (на месте современной Екатерининской площади). В 1796 г. учреждена биржа для международной торговли.

В 1795 г. по итогам первой переписи населения в Одессе проживало «2 349 душ обоего пола, кроме дворян и служащих». В основном значительную часть составляли беглые крестьяне, записавшиеся в мещане – 566 человек, так называемые, «казённые поселяне» — 300, мещане из разных губерний – 613, евреи – 240, греки – 224, болгары – 60, купцы разных гильдий – 146. В 1797 г. в Одессе проживало уже 3455 человек, в 1814 г. 20 тысяч человек, в 1829 г. 53 тысячи, в 1852 г. 97 тысяч, в 1859 г. 111 тысяч, в 1875 г. 193 тысячи, в 1897 г. 404 тысячи, в 1914 г. — 669 тысяч человек. Чтобы оценить этот масштаб, достаточно сказать, что спустя столетие в современной Одессе со всеми её спальными районами и новостройками проживает один миллион человек.

В составе населения преобладали украинцы, русские и евреи. Много было также болгар, молдаван, греков, итальянцев, французов, немцев, голландцев и др. национальностей. С самого начала (и даже до него) Одесса была многонациональным городом.

В 1798 г. был утвержден герб города — «щит, разделенный на 2 половины, вверху, на золотом поле — двуглавый орел, внизу — якорь о четырёх лапах».