Екатерининский собор был основан 30 августа 1781 года и является старейшей постройкой на территории бывшей Херсонской крепости. Собор заложен И. Ганнибалом, строился московским архитектором И.М. Ситниковым. Возводили его с 1781 года по 1786 год из бледно-желтого ингулецкого известняка в стиле русского классицизма с четырехколонным портиком у западного фасада. Завершал строение невысокий купол. В наружных нишах были помещены шесть скульптурных изображений святых. Иконостас выполнялся в западноевропейской традиции петербургскими мастерами, иконостас не сохранился, часть икон находится в собрании Херсонского художественного музея им. Шовкуненко. Собор был освящен 17 мая 1786 года.
Через год его посетила императрица Екатерина II, в присутствии которой был отслужен молебен. На «царском месте» находилось кресло, которое было приготовлено для императрицы. По ее повелению на фронтоне главного фасада была выполнена надпись: «Спасителю рода человеческого Екатерина II посвящает», в связи с чем собор носит еще одно название – Спасский.
23 ноября 1791 года по указанию Екатерины II в подвальном склепе внутри собора были погребены останки князя Г.А. Потемкина-Таврического, покровителя и создателя Херсона и Черноморского флота. Вокруг собора находятся могилы современников Г.А. Потемкина, захороненные по его распоряжению. В годы русско-турецкой войны 1787-1791 годов в ограде собора был создан мемориал с могилами павших героев.
К 1800 году западнее собора, по проекту И.Е. Старова была построена каменная колокольня, которая спустя два года пострадала во время землетрясения. Рядом с ней в 1806 году была возведена временная деревянная, с большим 112-пудовым колоколом, подаренным Екатериной II. Колокольня служила до окончания строительства новой каменной колокольни, существующей и поныне.
В мае 1922 года из Екатерининского собора были изъяты ценности весом более 40 кг, в конце декабря 1929 года были сняты колокола, разобран иконостас, часть икон передана в Херсонский краеведческий музей. В мае 1930 года в Екатерининском соборе открылся антирелигиозный музей, который вскоре был закрыт. Храм стал использоваться под зернохранилище. В августе 1941 года Екатерининский собор вновь был освящен и открыт для верующих. Из уцелевших частей прежнего иконостаса был собран новый, возвращены некоторые старые иконы.
С 1945 года по 1947 год Херсонская кафедра из Успенского собора была перенесена в Екатерининский собор. После войны храм действовал до 1962 года, затем был закрыт, большая часть церковной утвари передана в Свято-Духовский собор. Здание собора использовали для хранения дров, позже – под склад облкниготорга. Некоторое время он пустовал, затем в августе 1968 года ему присвоили категорию «памятник республиканского значения» и стали использовать как экскурсионный объект. В первой половине 1969 года на фасаде собора были отреставрированы скульптуры Апостолов Петра и Павла. В 1970 году в здании собора был открыт Дом пропаганды Херсонской областной организации Общества охраны памятников истории и культуры. В нем действовал выставочный зал и кинолекторий, проводились музыкальные вечера.
В начале 1980-х годов по старым чертежам были восстановлены два верхних разрушенных яруса колокольни, позже установлен позолоченный крест. Но в 1989 году здание собора из-за аварийного состояния было закрыто.
25 августа 1991 года храм был возвращен Церкви, в нем стали производиться реставрационно-восстановительные работы и совершаться богослужения. В 2007 году в соборе был установлен новый иконостас.
