Однако к моменту основания города ни один храм даже не был заложен. Построили только временную деревянную церковь в честь святого Николая, но она никак не соответствовала тем перспективам, которые «светили» юной Одессе. Было решено начать строительство каменной церкви, к которому митрополит Гавриил привлек архитектора, инженера-капитана Викентия Ванрезанта. И поздней осенью 1795 года рядом с временным Николаевским храмом митрополит освятил закладку новой церкви.
Однако строительство храма началось гораздо позже — через девять лет, когда Ришелье издал приказ «приступить к постройке соборной церкви во имя Святителя и Чудотворца Николая». Надзор за работами поручили архитектору Франциску Фраполли.
Вскоре здание собора уже возвышалось на центральной площади города, продолжались только внутренние отделочные работы. Денег на них катастрофически не хватало, поэтому даже иконостас пришлось перенести из старой деревянной церкви.
Весной 1808 года архиепископ Платон освятил новый храм: главный алтарь — во имя Преображения Господня, правый — во имя Святого Николая Мирликийского, а левый — в честь Святого Спиридона. С тех пор собор стал называться не Николаевским, а Спасо-Преображенским.
Деревянная Николаевская церковь выглядела рядом с величественным зданием убого, и ее решено было снести. Старую колокольню, правда, оставили. Причина была обычной — недостаток средств на строительство новой.