В 1792 года на окраине Херсона при городском кладбище была освящена часовня во имя Всех Святых. В ее стенах отпевали умерших херсонцев и воинов, отдавших жизнь при защите Херсона. Когда город стал губернским, власти приняли решение о строительстве на кладбище большого каменного храма. Церковь строилась с 1804 по 1808 год в стиле классицизма и была освящена в Неделю Всех Святых.
С 1882 по 1884 год в храме проводились капитальные работы: колокольня и его трапезная часть были перестроены и удлинены. 2 декабря 1884 год епископом Новомиргородским Николаем (Заркевичем), викарием Херсонской епархии, церковь была освящена. В память этого события по сей день под престолом Всехсвятского храма хранится крест, на котором отмечены имена участников освящения, а также встроен ковчег с мощами в верхней части креста.
После революции 1917 года Всехсвятская церковь была единственной из православных храмов Херсона, которая ни разу не закрывалась властями, с 1930-х г. по военные годы. В мае 1922 года из храма были изъята вся наиболее ценная церковная утварь, богослужебные книги и принадлежности, а в конце декабря 1929 года были сняты колокола.
В последние годы были произведены капитальные внешние и внутренние работы в самой церкви и на ее территории. Позолочен трехъярусный иконостас, расписаны стены храма, установлена новая риза на святой престол в алтаре. Старое покрытие пола заменено на светлый болгарский мрамор, обновлена крыша, покрытие колокольни украсила медная лакированная «чешуя». На колокольне установлены восемь воронежских колоколов от 500 кг и меньше, в 2003 году был приобретен самый большой колокол весом 1100 кг.
По материалам официального сайта pravoslavie.ks/ua
