A small collection of palaemonoid shrimps, mainly Pontoniinae, from New Caledonian waters of over 100 m depth, has been studied and found to represent 27 taxa, including eight new species of Periclimenes, one new species of both Periclimenaeus and Mesopontonia, and three specimens, including a single ovigerous female, representing a new genus, Amphipontonia kanak. Seven species were recorded from New Caledonian waters for the first time. The species of Periclimenaeus, from 370-450 m, represents the greatest depth from which this mainly shallow-water genus has been reported. Two species, a Periclimenes and a Mesopontonia, both new, were found together in association with a hexactinellid sponge host, Phoronema sp., the first reported association of pontoniine shrimps with a hexactinellid host. Another new Periclimenes, with a remarkable pectinate ambulatory dactylus, is also possibly associated with the "living fossil" crinoid, Gymnocrinus richeri. The present study increases to 57 the number of palaemonoid shrimps known from Indo-West Pacific marine waters exceeding 100 m depth, and clear1y indicates that these shrimps are quite well represented in deeper tropical seas. A list of the Indo-West Pacific palaemonoid shrimps known from over 100 m depth, with a new key to the deep-water Indo-West Pacific species of the genus Periclimenes is provided.