Из воронежских некрополей, которые сохранились, этот является самым древним. Генеральный план развития Воронежа утверждён в 1774 году, а на плане города 1773 года кладбище уже обозначено. Скорей всего, возникло оно в самом начале 1770-х.
Архитектор С.И. Соколов разработал проект кладбищенской церкви. Построена она была в 1838 году из камня, имела приделы Казанской Божьей Матери, а также святых воронежских епископов Митрофана и Тихона. Называлась она церковью Сошествия Святого Духа, но была известна также как Троицкая. Служила церковь одновременно приходским храмом для северной окраины города и для Троицкой слободы. Рядом с нею приютилась богадельня, каменное здание, как сказано в документах, «о двух покоях». До нашего времени оно не сохранилось, как и церковь, которую закрыли в 1934 году, а в 60-х полностью разрушили.
Много похоронено здесь участников Отечественной войны 1812 года. Например, участник Бородинского сражения и битвы при Лейпциге капитан Мягкий И.С.. Автор «Рассказов русского воина», участник нескольких заграничных походов, Итальянского похода Суворова в частности, полковник Старков Я.М.; участвовавший в заграничных походах русской армии, а также во взятии Парижа генерал-майор Халютин Д.И. и многие другие.
Хоронили на кладбище также погибших в первой мировой офицеров, деятелей науки и культуры. Так, на этом кладбище похоронен автор архитектурного проекта Троицкой церкви С.И. Соколов, а также земский деятель А.И. Веревкин. Этот учёный-ветеринар в 1912 году основал в Воронеже ветеринарно-фельдшерскую школу.
Захоронены на Терновом кладбище также общественные деятели, участники революционного движения. Среди них известный юрист Сергей Александрович Петровский, присяжный поверенный, бывший депутатом ІІІ государственной думы. Есть в Воронеже улица Н.И. Таранченко. Этот студент Московского университета погиб в Воронеже в 1905 году, при еврейском погроме 21 октября. Имя комсомолки, расстрелянной в 1919 году, Марии Копыловой, тоже носит одна из улиц города. И Мария Копылова, и Н.И. Таранченко похоронены на Терновом кладбище.
Официально закрыли некрополь в 1926 году, но хоронить продолжали до 40-х годов. Современная школа №16 построена на месте колокольни разрушенной Троицкой церкви, её спортплощадка занимает часть территории кладбища. После Великой Отечественной войны начался снос надгробий кладбища и продолжался до 60-х годов. И только с 1992 года кладбище охраняется государством как памятник истории.
Учитель истории С.А. Наговицын организовал учащихся школы №16, и в 2002 году они в некоторой мере благоустроили кладбище. Теперь его территория уже не похожа на запущенный парк. В 2008 году архитектор В.Г. Фролов разработал проект реконструкции кладбища, запланировано создать на его базе полноценный мемориальный комплекс.
