Комплекс катакомб святого Калліста формувався протягом II–IV століття на базі декількох зон поховань, що раніше існували і поступово розширювались та злилися в єдину мережу до кінця IV століття. У числі первинних базових кладовищ можна згадати власне катакомби Калліста, а також крипту Луціни, цвинтар святого Марка, Марцелліна, Дамасія і Бальбіни.

Спочатку територія майбутніх катакомб знаходилася у приватних руках, потім власники земель, ставши християнами, передали свої володіння церкві. Рішення облаштувати тут кладовище для всіх членів християнської громади Риму належить римському єпископу Зефірину. Організація та управління комплексом поховань були доручені диякону Каллісту. До обов'язків Калліста було поставлено гідне поховання кожного померлого християнина, при цьому похорон бідних здійснювалися за рахунок церкви.

Калліст, що став після смерті Зефіріна його наступником, значно розширив і упорядкував катакомби протягом свого понтифікату, так що в церковній свідомості цей похоронний комплекс тісно пов'язаний з ім'ям Калліста.

Найстародавнішими частинами катакомб Калліста є крипта Луціни та секції, що включають крипту Пап, крипту святої Цецилії, кубікули Святих Тайн. У кінці III століття до них були приєднані секції святого Гая і святого Євсевія, а у другій половині IV століття — святого Ліберія.

Катакомби з самого свого виникнення грали в житті церковної громади подвійну роль. З одного боку, це був цвинтар, на якому належним чином міг бути похований кожен християнин, з іншого, катакомби стають місцем паломництва до гробниць шанованих мучеників. Згідно з традицією, у дні пам'яті мучеників (переважно в дні їх мученицької смерті — народження у вічне життя) на їх гробницях відбувалася літургія, і читалися мученицькі акти — розповіді про їх героїчний свідоцтві про Христа. До гробниць мучеників приходили і в інші дні, про ці приватні паломництва свідчать численні графіті — молитовні звернення до святих на стінах катакомб.

У IV столітті підземне кладовище були прикрашене папою Дамасієм, ним же написані численні віршовані епітафії, поміщені в найважливіших місцях катакомб.

Починаючи з V століття, в Італії панує хаос, пов'язаний з падінням Римської імперії, виникненням і падінням варварських держав. Життя Риму і відповідно Римської церкви зосереджується всередині Авреліанових стін, подорож за межі яких стає небезпечним. В зв'язку з цим, протягом V–IX століття з катакомб були вивезені мощі всіх шанованих святих.

Так, в 609 році папа Боніфацій IV перевіз в Пантеон, перетворений в церкву «Божої Матері і мучеників» (лат. Santa Maria ad Martyres), 28 возів з мощами. Похорони за межами Авреліанових стін також стали небезпечними. У результаті вже до IX століття катакомби виявляються настільки покинутими, що папі Пасхалію I з величезними труднощами (а, за переказами, ще й за допомогою самої святої) вдалося знайти тут мощі святої Цецилії.

Протягом наступних століть катакомби святого Калліста були повністю забуті. Їх нове відкриття відбулося у 1854 році. З цього часу катакомби активно вивчаються.

В наш час[коли?] для відвідування прочан і туристів відкрита лише незначна частина катакомб святого Калліста — друга ділянка (з чотирьох виявлених) рівнів катакомб. Всього ж площа території, під якою знаходяться досліджена частина цих катакомб, перевищує 36 га. Загальна довжина досліджених коридорів становить близько 21 км. Кількість виявлених поховань на сьогодні — близько 500 000. Втім, значна частина катакомб святого Калліста залишається, можливо, невідомою. Досі невідомо, наприклад, чи з'єднуються ці катакомби з прилеглими катакомбами святого Себастіана і святої Домітілли.