This new settlement was given the name Odessa.

The city's name came about as a result of an error. It was meant to be named after the ancient Greek city of Odessos or Ordissos, which was believed to have been founded in the
vicinity. Actually, it was somewhere near the present day town of Varna in Bulgaria. But Catherine the Great liked "Adessa" — as it is pronounced by the Russians and Ukrainians.

In 1803, Tsar Alexander I appointed a young French emigrant, then 36 years old, the Duke de Richelieu to be the gradonachalnik, or the mayor, of Odessa. Eighteen months later, in 1805, the Tsar enlarged his authority by appointing him to serve simultaneously as the governor of the three provinces of Novorossiya. In the 11 years of his administration, the Duke de Richelieu acquired an extraordinary reputation for statesmanship and sense, both abroad and in Russia. Clothed inexplicable in a toga, his statue now points out to the sea, presumably to indicate the source of Odessa's wealth. Duke left Odessa on September 26, 1814 for France. Even after his return to France to serve as prime minister under the restored monarchy, he retained cordial ties with the Imperial Russian Court and with the Russian ambassador to France, Pozzo di Borgo.