Batellopsis paula gen. et sp. nov., a new hexactinellid-associated alpheid shrimp, is described based on a single specimen collected at a depth of 477–503 m north of Île des Pins, New Caledonia. Batellopsis gen. nov. is part of a clade of four genera all containing  hexactinellid-associated species, for which a molecular phylogeny is presented. The evolution of several morphological characters, including orbital teeth, bulge-fossa system on the fingers of the first pereiopod chela and groups of microserrulate setae on the second pereiopod chela, is discussed in the light of the obtained phylogenetic results.