Официальной датой открытия Всесвяцкого кладбища считается 1838 год. Стихийные захоронения встречались здесь и раньше, однако статус кладбища часть земли за городской чертой получила лишь после закрытия Фоминского погоста.
Новое Всесвяцкое кладбище, как и положено, началось с обнесения его территории оградой. Неподалеку находились выгонные земли, и временами на погост по привычке забредал скот. За всю историю кладбища оград было как минимум три. В 1928 году горисполком издал постановление приступить к постройке кирпичной ограды вокруг кладбища. Одна из оград имела на главном входе прекрасные чугунные ворота с иконой над входом.
В 1837 году исполняющий обязанности наказного атамана Григорий Рашпиль начал собирать деньги на строительство церкви Всех Святых. Большую часть средств пожертвовал войсковой старшина «вино-водочный и рыбный король» Посполитаки. Храм строился по проекту архитектора Елисея Денисовича Черникова. Церковь была небольшая, деревянная, с отдельной колокольней на столбах и располагалась в центре кладбища. По одним источникам, освящение церкви состоялось в 1848 году, по другим - только в 1852.
При церкви находился построенный также на общественные деньги караульный турлучный дом «о двух покоях и печи». В карауле несли круглосуточно дежурство нестроевые казаки. Кладбище охраняли сторожевые собаки, которых на ночь спускали с цепи. Известны случаи, когда собаки «летали» припозднившихся хулиганов и ночных воришек.
В конце 19 века на кладбище ввели оплату за место захоронения. Территорию разбили на шесть тарифных участков. Быть похороненным в центре стоило 20 рублей. По мере удаления стоимость снижалась до десяти, пяти и трех рублей. Последние два участка были отведены для бедняков и умерших от эпидемий и заразных болезней. Они располагались при входе на кладбище с улицы Северной с левой стороны. В те годы основной причиной смертности была антисанитария, которая влекла за собой различного рода болезни.
В плане города Екатеринодара 1910 года Всесвяцкое кладбище составляла площадь приблизительно 200 на 300 саженей (427 на 640 метров). Расположение захоронений на нем напоминало слегка наклоненный влево православный крест. Севернее располагалась скотобойня, кирпичный завод, ассенизационный обзор. С противоположной от обоза стороны к Всесвяцкому погосту примыкали караимское, татарское, еврейское, военное кладбища, а также кладбище для заразных больных. Последних было особенно много в 1892 году, во время эпидемии холеры. Сейчас сохранилась лишь часть еврейского кладбища, а остальные могильники поглотил частный сектор.
В 1913 году Городская дума заказала новый план Всесвяцкого кладбища. Его составитель научно-общественный деятель коммунального хозяйства П.В. Миронов. Уже тогда не было свободного места и предпринимались попытки что-либо построить.
К 1925 году стали использовать под захоронения даже двадцатиметровую санитарную полосу. Она вошла в фонд кладбища как дополнительный, седьмой его сектор. На нем хоронили погибших и умерших во время Гражданской войны и в первые годы советской власти.
Участок, расположенный впритирку к казармам, назывался братским кладбищем, или белым. Все оно было в белых железобетонных крестах. Сейчас на месте белого кладбища построена улица Аэродромная.
В годы после революции тысячи могил были разграблены, осквернены, все, что представляло ценность, хранится в тайниках коллекционеров. Был период в 1934 году, когда кладбище закрывалось на месяц по распоряжению НКВД. В это злополучный месяц были вскрыты многие усыпальницы. Также в 30-е годы была разрушена церковь Всех Святых.
Время шло, а проблемы оставались нерешенными. Систематически нарушались санитарные нормы захоронений, участки кладбища зарастали деревьями и сорной травой. Повсюду виднелись свалки мусора и нечистот. Многие памятники находились в плачевном состоянии.
26 декабря 1964 года горисполком Краснодара вынес решение о закрытии Всесвяцкого кладбища. Также в этом году прекратились захоронения на кладбищах по улице Бабушкина.
Через 25 лет на месте Всесвяцкого кладбища планировалось возвести парк и Дворец бракосочетаний, но общественность не позволила сделать этого.
К 40-летию Победы (1985 г.) была произведена реконструкция кладбища. По улице Северной был возведен мемориал. В спешном порядке производились перезахоронения: могилы погибших в годы Великой Отечественной войны были перенесены ближе к мемориалу, а дореволюционные в глубь кладбища. Многие до сих пор не знают, где теперь покоятся их родственники.
Список известных людей, похороненных на этом кладбище: