A new species, Paranaxia keesingi sp. nov., is described based on specimens collected in northern Australia. The new species differs from its only congener, P. serpulifera (Guérin, 1832, in Guérin-Méneville 1829-1837), by several characters including carapace setation, sternal cavities, absence of a subhepatic spine, presence of a sharp spine on the posterodistal angle of the cheliped merus, relatively shorter chelipeds, and longer and more slender ambulatory legs. Morphological separation of the two species is supported by 12s rDNA sequence divergences of 7.4-8.2%. Like P. serpulifera, the newly described species exhibits direct development with females carrying juvenile individuals under the pleon. Both species are sympatric, but Paranaxia keesingi sp. nov. is found in deeper waters than P. serpulifera.