Cestodes were collected from deep-sea sharks caught off New Caledonia, South Pacific. Vittirhynchus squali n. g., n. sp. (Trypanorhyncha: Gilquiniidae) is described from the spiral valve of Squalus melanurus Fourmanoir & Rivaton. The new genus possesses four bothria and a typical heteroacanthous metabasal armature but has a file of three macrohooks forming a short chainette on the internal surface of the basal armature. Sagittirhynchus aculeatus n. g., n. sp., from the spiral valve of Centrophorus sp. (undescribed), also has four bothria and a typical heteroacanthous armature but lacks a distinctive basal swelling and has the final hooks of each principal row prominently enlarged. Gilquinia minor n. sp., from the spiral valve of Centrophorus sp. (undescribed), is distinguished by the presence of only five hooks per principal row compared with eight in congeners. Gilquinia sp. is reported from Squalus melanurus. G. robertsoni Beveridge, 1990 is reported from S. megalops (Macleay).