Вперше нова назва міста зустрічається 10 січня 1795 року. Існує декілька версій про походження назви «Одеса».
Має місце факт, що в кінці XVIII сторіччя була традиція називати міста на завойованих у турок територіях грецькими іменами (наприклад, Севастополь, Тирасполь і т. п.). Тому можна припустити, що Одесу назвали на честь старогрецької колонії, що розташовувалася в північному причорномор’ї Одесос, в ті роки припускалось, що існувала вона неподалік від Одеської затоки (пізніше археологи знайшли цю колонію неподалік від болгарського міста Варна).
Інший варіант — етимологічний.
По одній з легенд, результатом царських дебатів про відсутність прісної води поблизу вибраного для будівництва місця, назвою міста, волею імператриці Катерини II, став прочитаний навпаки французький вираз «assez d’eau» (води досить). Дана версія офіційною історіографією відкидається.Легенда свідчить, що нова назва довго не приживалася і люди, як і раніше, називали Одесу Хаджибєєм. Тому для кращого засвоєння населенням нової назви, влада застосувала наступний метод. На всіх міських заставах козаки питали в’їжджаючих селян: «Куди шлях тримаєте?» І якщо слідувала відповідь «В Хаджібей», козаки цю людину просто лупцювали. Метод виявився дієвим і незабаром вже всі іменували місто Одесою.