Kirkegården blev indviet i 1818.

1. januar 1885 var Søndre Kirkegård blevet lagt ind under kommunens administration, forudsat at kirkegården fortsat skulle være i brug de næste 42 år, altså til den 1. januar 1927. Kommunen opfyldte forpligtigelsen, og sidste begravelse på Søndre Kirkegård fandt sted den 21. november 1926, da 77-årige Johanne Nielsine Petersen (født Christiansen) - enke efter slagtermester Johan Petersen - blev begravet fra Skt. Pauls Kirke. I alt nåede omkring 13.000 mennesker at blive begravet på kirkegården – høj som lav.

En stor del af kirkegården var dog allerede blevet sløjfet i starten af 1920’erne til fordel for anlæggelsen af Park Allé (1919-1920) og udvidelsen af Sønder Allé (1924-1925). Formindskningen af kirkegården gjorde, at gravsteder enten måtte flyttes eller sløjfes.

Efter sidste begravelse havde fundet sted på kirkegården, var planen at omdanne området til park. I 1930’erne blev det dog besluttet, at den gamle kirkegård skulle lægge jord til byens nye rådhus og rådhuspark.