Na metade do século XVIII, a maior parte das igrejas de Paris possuía seus próprios cemitérios. Entretanto, o crescimento da cidade acumulou gerações e mais gerações de despojos funerários para os quais os cemitérios não ofereciam mais espaço.

Em 1780, o cemitério "des Saints-Innocents", o mais importante da cidade, foi fechado, por demanda da população. A lotação do cemitério era tal que a população vizinha estava adoecendo devido à contaminação provocada pelo excesso de matéria orgânica em decomposição.

No dia 9 de novembro de 1785, o Conselho de Estado francês decidiu pela necessidade de reformular o sistema de cemitérios de Paris e pela imediata tomada de providências. Novos cemitérios foram construídos na periferia da cidade, mas restava a preocupação do que fazer com os cemitérios superlotados já existentes.

A ideia de usar os túneis abandonados das pedreiras parisienses é creditada ao chefe de polícia, general Alexandre Lenoir, e levada a cabo por ordem de seu sucessor, o sr. Thiroux de Crosne.

A escolha do local apropriado e execução da tarefa ficou a cargo do "Service des carrières" cuja tradução poderia ser "Serviço das Pedreiras", na realidade, um órgão governamental criado em 4 de abril de 1777 para zelar pela segurança e consolidação do subsolo parisiense, tão cheio de túneis e cavernas com constantes riscos de desabamentos.

Sob orientação de Charles Axel Guillaumont, inspetor geral dos túneis de Paris, as primeiras ossadas transferidas saíram do cemitério Saint-Nicolas-des-Champs após as Catacumbas terem sido abençoadas, em 4 de abril de 1786.

Inicialmente, as ossadas foram jogadas de qualquer modo nas catacumbas.

Somente na época do império francês (a partir de 1810) que, sob orientação de Héricart de Thury (1776-1854), as ossadas foram dispostas nos corredores das Catacumbas com certa criatividade artística. Ossos longos, como fêmur e tíbia, foram colocados à frente, formando verdadeiras paredes de ossos, adornadas com os crânios em desenhos geométricos. Por trás dessas paredes de ossos, foram depositados os ossos menores e mais irregulares.

Durante a Segunda Guerra Mundial, membros da Resistência Francesa utilizaram assiduamente os túneis de Paris. Os alemães também serviram-se dos túneis, chegando a construir bunkers e casamatas nas suas galerias.

Na segunda metade do século XX, como sempre, os subterrâneos de Paris foram usados por grupos das mais diversas ideologias. Grupos de ativistas políticos, religiosos, artistas, aventureiros, usuários de drogas e vários outros serviram-se dos subterrâneos para seus propósitos, o que ocorre ainda hoje.

Os subterrâneos de Paris também foram utilizados para passagens de cabos telefônicos, de TV por assinatura e de acesso à Internet. Entretanto, devido a inúmeros casos de vandalismo e dificuldades de acesso, tais cabos foram transferidos para tubulação específica mais superficial e protegida.

A parte dos subterrâneos ocupada pelo ossuário continua reservada e é aquela à qual os turistas têm acesso com total segurança.

Com a especulação imobiliária e necessidade de reforço do subsolo para segurança das edificações, uma média de 5 km da rede de túneis existente tem sido bloqueada anualmente por estruturas de cimento.