A new species of Nybelinia Poche, 1926, N. queenslandensis sp. n. (Cestoda: Trypanorhyncha) is described from sharks, Carcharhinus melanopterus (Quoy et Gaimard, 1824) from the coast of northeastern Queensland, Australia. Morphological features of the 46 known species of Nybelinia Poche, 1926 are tabulated and the new species is differentiated from all known taxa that are adequately described on the basis of having a homcomorphous armature, metabasal hooks 20-25 pm long, tentacles 0.07-0.09 mm in diameter, short bulbs (0.38-0.45 mm) and craspedote segments with the testes encircling the female genital complex. The fine structure of the scolex microtriches, frontal and rhynchodeal glands, tentacles and hooks, sheath and retractor muscle is described and compared with that of other trypanorhynchs.