В 1785 году купцы и мещане Купеческого предместья Херсона обратились к архиепископу Никифору с просьбой построить храм в честь Успения Пресвятой Богородицы с двумя приделами: Святого Николая Чудотворца и Святой Варвары. Это было необходимо, так как существующая церковь Святой Софии была греческой, и службы в ней велись на греческом языке. Храм заложили в 1786 году в центре предместья на Греческой площади. Главными благотворителями стали купцы Петр Фендриков и Иван Сизарев. Русско-турецкая война 1787 года задержала строительство, поэтому временно была перенесена деревянная церковь Святого Архистратига Михаила, освященная в 1788 году. Через десять лет её разобрали, так как 14 апреля 1798 года освятили Успенскую церковь. Она была крестово-купольной, длиной 46 метров, шириной 31 метр и высотой 40,5 метров. К ней пристроили деревянную колокольню высотой 45 метров. Приделы освятили позже: южный в честь Николая Чудотворца 16 мая 1799 года и северный в честь Святой Варвары. По преданию, строительство завершилось благодаря пожертвованию одного из запорожцев. В 1828 году, после перевода учреждений Херсонского адмиралтейства в Николаев, Успенская церковь стала городским собором. В 1833 году деревянная колокольня была заменена на каменную, а в 1897 году на ней установили железный шпиль с крестом.

Вокруг храма со временем вырос ансамбль церковных построек. Перед входом, со стороны улицы Ришельевской, были построены два двухэтажных дома: в 1822 году на севере и в 1829 году на юге. Первый сдавался в аренду, а во втором находились причт и Духовное правление, а с 1849 по 1874 год, Духовное училище.

В 1853 году архиепископ Иннокентий добился открытия викариатства в Херсонской губернии, и Успенский собор стал кафедральным. Первым викарным епископом был Поликарп, занимавший этот пост с 5 июля 1853 года по 12 июля 1858 года. В 1859-1861 годах собор капитально отремонтировали, вокруг него появилась ограда с металлической решеткой и тремя воротами.

В 1867-1868 годах построили двухэтажный дом для священников, а в 1896 году, дом читальни-библиотеки и Аудитории религиозно-моральных чтений. В 1850-х годах произошло два важных события: 8 мая 1852 года прибыл первый крестный ход с Касперовской иконой Богоматери, а 26 октября 1855 года собор посетил император Александр II. После окончания Крымской войны он направил благодарственную грамоту жителям Херсонской губернии. Среди благотворителей собора известны Яков Дорошенко, Иван Волохин и его сын Александр Иванович Волохин, а также купец Даниил Галухин.

Успенский собор, крупнейший в Херсоне, был прост в архитектуре, но богато украшен внутри. Грандиозный иконостас, высотой 17 метров, содержал 50 икон. Сохранилась только одна, Пресвятая Богородица. Первые иконы, вероятно, написаны киевскими мастерами. В конце 1850-х годов Тимофей Толмачевский расписал интерьер в византийском стиле, а херсонский художник З.И. Рябков расписал приделы и фрески храма. Ничего из этого не сохранилось.

В советские годы собор постигла судьба многих церквей. В 1922 году изъяли ценности, в 1929 году сняли колокола, в 1930 году собор закрыли и передали под спортивный клуб, уничтожив интерьер. Во время оккупации храм действовал, но в 1944 году его снова закрыли и сделали Дворцом физкультурников. С 1945 по 1993 год в соборе находился спорт-клуб «Петровец». В сентябре 1993 года храм вернули Украинской православной церкви и начали восстанавливать.

Успенский кафедральный собор является памятником архитектуры XVIII века и входит в охранную зону исторической застройки города.