Население Одессы в первое столетие росло быстрыми темпами и 80-е годы XIX века перевалило численностью за 300 000 человек. Заселялись все новые и новые районы города. Жители районов Ближних Мельниц и Воронцовки, ощущая необходимость постройки церкви в их местности, в 1884 году обратились к епископу Херсонскому и Одесскому Никанору с прошением о строительстве приходского храма. Разрешение было получено, но на устроение временного молитвенного дома во имя св. Александра Невского. Точная дата освящения молитвенного дома, с присвоенным правом приходской церкви, неизвестна. Приход его составляли следующие улицы: Болгарская, Малороссийская, Хуторская, Сиротская, Воронцовка, Ближние Мельницы и Степовая до Конной площади включительно.
Первым наставником стал священник о. Петр Лозинский, старостой, летом 1885 года, прихожане единодушно избрали домовладельца М.М. Русского.
С открытием богослужений в Александро-Невском молитвенном доме начался сбор пожертвований на строительство проектируемого храма. Однако, многие жители, особенно богатые домовладельцы, воздерживались жертвовать, по той простой причине, что городом еще не было определено конкретное место под постройку.
В другой раз, с прошением отвести место под строительство церкви на переименованной Больше-вокзальной площади, прихожане обратились в городскую управу. Здесь же излагалась и другая просьба, о принесении городом в дар молитвенному дому св. Александра Невского второго проекта храма, победившего в прошедшем конкурсе и хранившегося в городской управе. По мнению прихожан, это позволило бы "избавиться от лишних расходов на составление нового”. Прошение было полностью удовлетворено, а план постройки утвердил Высокопреосвященный архиепископ Никанор, возведенный в этот сан 20 марта 1886 года.
Получив активную поддержку со стороны церковного и городского руководства, с новой силой возобновился сбор средств на постройку храма. И, здесь возникла фигура полковника и одесского домовладельца И.С. Федоровского, внесшего очень значительную сумму, в размере 48 тыс. руб., отчего все строительство теперь могло вестись на основные деньги жертвователя, хотя городом первоначально и была определена смета в 35 тыс. руб.
Федоровский родился в 1814 году, получил образование в Харьковской гимназии, по окончании ее был зачислен в университет, который так и не закончил. Бросив дальнейшую учебу, он поступил в Смоленский уланский полк, где началась его военная карьера. Уйдя в отставку и поселившись в Одессе, скопил немалый капитал. Будучи глубоко верующим человеком, он нашел достойное применение своим сбережениям – пожертвовал их на строительство церкви.
Закладка храма состоялась в 1887 году. Строительство продвигалось быстро и без задержек, что позволило подрядчикам к середине 1888 года практически закончить постройку церкви. Трехпрестольный храм красавец (архитектор А.Д. Тодоров), выдержанный в классическом стиле, украсил своею постройкою площадь и был виден далеко в округе. Внутреннее убранство храма – прекрасный иконостас, лепка, отдельные детали исполнены были по тем же канонам. Живопись иконостаса, иконы, евангелисты в парусах были написаны в старо-византийском художественном стиле.
Настал день освящения нового храма, 25 сентября 1888 года это торжество, а затем и божественную литургию совершил архиепископ Никанор. Несколько тысяч человек заполнили церковь и площадь перед ней. Воздух рассекали слова молитвы, одновременно с разлетающимися в разные стороны каплями святой воды. Храм освятили во имя св. Алексия , человека Божия.
Причт Алексеевского храма состоял из настоятеля в сане протоиерея, одного священника, дьякона и псаломщика. В разные годы в храме служили протоиереи Жураковский, Михаил Клопотов, священники Михаил Ремизов, Николай Боголюбов.
При церкви, еще во времена существования молитвенного дома, открылась двухклассная церковно-приходская школа для мальчиков и девочек. В 1905 году в ней обучалось 180 детей. Под покровительством храма находились также три народных училища, техническое и железнодорожное. В 1890 году распоряжением епархиального руководства при церкви было утверждено приходское попечительство.
В начале 90-х годов XX века был вновь создан и зарегистрирован приход Алексеевской церкви, который временно разместился в одном из помещений венерологического диспансера. Стараниями епархии и прихожан храм имеет просторное и великолепно устроенное помещение. Чудом сохранившаяся табличка со стены разоренного храма, прикреплена снова у входа в церковь. На ней памятная надпись в честь благотворителя И.С. Федоровского, на чьи средства был возведен храм во имя св. Алексия.
Весной 2001 года вцентре Алексеевского сквера бал заложен новый большой храм, уже закончен "нулевой цикл строительства", возводятся стены. Недалек тот день, когда на бывшей Большевокзальной площади вознесутся вверх купола Алексеевской церкви, а колокола окласят округу своим звоном.
