L'ús d'aquestes desgastades mines, per a l'emmagatzematge d'ossos humans, va ser establert el 1786 per Monsieur Thiroux de Crosne, tinent general de la policia, i per Monsieur Guillaumont, inspector general de les mines; tot això degut principalment a l'excés de restes humanes que omplien els cementiris de la ciutat;[1] a la vegada, el districte de Les Halles patia de malalties degudes a la contaminació pel maneig inadequat d'aquests cadàvers, especialment en el cimetière des Saints-Innocents (Cementiri dels Sants Innocents).

Restes provinents del cementiri Saint Nicolas des Champs van ser els primers a ser traslladats. Cadàvers de les morts causades per desordres a la Plaça de la Grève, l'Hôtel de Brienne i la Rue Meslée, van ser posats en les catacumbes el 28 i 29 d'agost del 1788.

Aproximadament 15 mesos van ser necessaris per traslladar milions d'ossos provinents de multitud de cementiris, la qual cosa es duia a terme durant les nits, creuant la ciutat en carruatges, finalitzant en la dècada del 1870, acumulant les restes d'aproximadament 6 milions de parisencs.[2]

Les parets de les catacumbes estan cobertes per grafits, que daten des del segle xviii endavant. Victor Hugo va basar la seva cèlebre novel·la Els miserables en el coneixement que posseïa sobre el sistema de túnels que comprenen les catacumbes. El 1871 la comuna de París va assassinar un grup de monàrquics en una de les càmeres. Durant la Segona Guerra Mundial membres parisencs de la Resistència francesa van utilitzar aquest sistema de túnels.[3] D'igual manera, durant aquest període, soldats alemanys van establir un búnquer subterrani en les catacumbes, sota Lycée Montaigne , una escola secundària en el sisè arrondissement.