The first and foremost church in the city of Odessa, the cathedral was founded in 1794 by Gavril Bănulescu-Bodoni. Construction lagged several years behind schedule when the newly appointed governor of New Russia, Armand-Emmanuel de Vignerot du Plessis, Duc de Richelieu, employed the Italian architect Francesco Frappoli to complete the edifice.
The cathedral was designated the main church of New Russia in 1808 and was continuously expanded throughout the 19th century. The belltower was built between 1825 and 1837, and the refectory connecting it to the main church several years later. The interior was lined with polychrome marble, and the icon screen also was of marble.
Several churches in the region, including the Nativity Cathedral in Chişinău, were built in conscious imitation of the Odessa church. The cathedral was the burial place of the bishops of Tauride (including Saint Innocent of Kherson) and Prince Mikhail Semyonovich Vorontsov, the famous governor of New Russia.
The original structure was demolished by the Soviets in 1936. It was rebuilt starting from 1999. The new cathedral was consecrated in 2003. The remains of Vorontsov and his wife were subsequently reburied in the cathedral. There is a statue of him on the cathedral square. The cathedral bells are controlled by an electronic device capable of playing 99 melodies.