Sejak zaman Romawi, warga Paris biasanya memakamkan karib kerabatnya yang meninggal dunia di kawasan pinggiran kota, tetapi kebiasaan ini berubah setelah masuknya agama Kristen. Praktik Kristiani menganjurkan untuk menguburkan jenazah di bawah tanah suci gereja. Pada abad ke-10, tanah pemakaman di Paris semakin sempit akibat kota yang semakin padat. Pada abad ke-12, masalah ini diatasi dengan dibukanya ruang bawah tanah di bawah kota untuk menampung jenazah warga Paris. Namun, lambat laun pemakaman bawah tanah ini menjadi semakin penuh sesak dan menimbulkan masalah bagi sanitasi warga kota yang sumber air utamanya adalah air sumur. Pada abad ke-19, penggunaan katakomba sebagai tempat pemakaman dilarang setelah dibangunnya tiga tempat pemakaman umum di luar kawasan pusat kota.

Jenazah korban kerusuhan Place de Grève dan Rue Meslée dimakamkan di katakomba ini pada tanggal 28 dan 29 Agustus 1788. Jenazah Philibert Aspairt hilang di katakomba pada tahun 1793 dan ditemukan kembali 11 tahun kemudian. Dinding katakomba ini dipenuhi oleh grafiti pada abad ke-18. Victor Hugo menggunakan terowongan katakomba ini sebagai salah satu latar tempat dalam novelnya, Les Misérables. Pada tahun 1871, para komunar membunuh sekelompok monarkis di dalam salah satu ruangan katakomba. Selama Perang Dunia II, warga Paris memanfaatkan terowongan katakomba untuk bersembunyi. Juga selama periode ini, tentara Jerman mendirikan sebuah bunker bawah tanah di katakomba, tepat di bawah Lycée Montaigne.