Un veuf, Rondin (Michel Serrault), qui tient à Paris une petite librairie menacée par de vastes travaux d'excavation, s'alarme car sa fille de vingt ans, Marie-Hélène (Chantal Goya) a disparu sans laisser de traces. Il va à la police mais le commissaire Lalatte (Michel Galabru), qui prépare ses vacances, ne le prend guère au sérieux. Seul un facteur un peu benêt (Gérard Depardieu) vient en aide au libraire. Une série d'indices et d'incidents, dont la disparition d'un groupe de touristes au cours d'une visite des catacombes, amènent Rondin à conclure que la disparue se trouve dans les profondeurs du sous-sol de la ville. Il part donc à sa recherche, tandis que les travaux herculéens entrepris par le mégalomane ministre des Travaux publics (Charles Denner) sont en bute à d'étranges représailles venues d'en bas, tout en bas... plus exactement de Gaspard de Montfermeil (Philippe Noiret), chef débonnaire de ce peuple qui, on le sait, vit sous Paris depuis des siècles.