Kaip ir kiti industrializacijos laiku staigiai išaugę miestai, Paryžius irgi susidūrė su didelėmis problemomis – o tarp jų buvo ir ligos bei mirtis. Gero gyvenimo viltys į miestą iš kaimo pritraukė būrius žmonių, o XVIII a. pabaigoje tai virto nemenka problema: nebeliko vietos kapinėse.
Pasakojama, kad XVIII a. vienos didžiausių Paryžiaus kapinių – Nekaltųjų kapinės (pranc. Les Innocents ) – iš tolo dvokė, nes negalėjo sutalpinti staigiai išaugusio mirusiųjų kiekio. Pasakojama, kad kvapas buvo toks baisus, jog kėlė pavojų net kvepalų prekybai. O 1780 m. gegužę kapinės tikrąja to žodžio prasme palūžo – kapinių rūsio siena sugriuvo, ir pavasario lietūs išplovė į išorę pusiau tesuirusius kūnus – kas žinoma, kėlė ne tik estetines, bet ir sanitarines problemas.
Artimiausiai mėnesiais miesto valdžia priėmė sprendimą uždaryti ne tik Nekaltųjų, bet ir visas miesto kapines. Daugiau jokių palaidojimų miesto ribose! Bet kadangi jau iki šiol palaidoti kūnai vis dar kėlė grėsmę sveikatai, miesto galvos nusprendė ištuštinti esamas kapines.
Laimei, egzistavo planas. Paryžiuje kažkada buvo daugybė kasyklų ir akmens skaldyklų, kurios tapo tobula vieta saugoti miesto mirusiuosius, ir 1787 ir 1814 m. visi kaulai buvo perkelti į žemės gilumas. Įėjimas į požeminius tunelius buvo įrengtas netoli senų miesto vartų, ir pavadintas „Barrière d'Enfer“ – laisvas vertimas reikštų daugmaž „Pragaro vartus“. Nors skeletai iš pradžių buvo sukrauti į požemius bet kaip, galiausiai buvo tvarkingai suskirstyti į vietas – ir tokiais liko iki šiol.
Tarp 6 milijonų griaučių galima rasti ir įžymybių palaikų – pavyzdžiui, nukirsdintuosius Revoliucijos veikėjus Georgesą Dantoną ir Maximilieną de Robespierre’ą, taip pat – folkloristą Charlesą Perrault, kuris užrašė tokias pasakas, kaip „Raudonkepuraitė“, „Pelenė“ ir „Miegančioji gražuolė“.
Šiandien Paryžiaus katakombos driekiasi 20 metrų gylyje ir apie 1,5 km jų atkarpa atverta turistams. Landžioti į gilesnes katakombų dalis draudžiama nuo 1955 m., bet adrenalino mėgėjai šio draudimo nelabai klauso ir per paslėptus įėjimus braunasi toliau – kas, žinoma, labai nerekomenduotina. Štai 2017 m. teko gelbėti tris paauglius, kurie žmonių kaulų pilnuose labirintuose pasiklydę buvo net tris dienas.