Four new skates of the genus Notoraja Ishiyama, 1958 are described from the rarely accessed, deep waters off New Caledonia, Vanuatu and Fiji islands, and the Norfolk Ridge. Three of these (N. alisae n. sp., N. longiventralis n. sp. and N. fijiensis n. sp.) are “velcro skates” which are characterised by their velvety dorsal and ventral surfaces, covered with fine denticles. Although similar in shape, they differ by their colour pattern, dermal armature, development of the lateral tail folds, and size of the pelvic-fin anterior lobe and nasal curtain. The description of the fourth species, Notoraja inusitata n. sp., is based on a juvenile male exhibiting some unusual features resembling those of other skate genera.