Pandanus grayorum Callm., Buerki & Gallaher (Pandanaceae) is newly described from the Wet Tropics of north-eastern Queensland in Australia. It is the second Australian species other than P. gemmifer H.St.John known to reproduce by axillary plantlets on aerial branches. It can be distinguished from P. gemmifer and P. solms-laubachii F.Muell. by the dimensions of its leaves, shape and dimensions of its syncarps, and by the morphology of its phalanges. The placement of P. grayorum in a molecular phylogeny confirmed morphological evidence and showed that the new species clusters with P. gemmifer and P. solms-laubachii in a clade closely related to the P. tectorius Parkinson complex. Pandanus grayorum is known from near the banks of the lower reaches of Mulgrave, Russell, Johnstone and Moresby rivers and associated subcoastal flood plains. Most collection records are from areas outside national parks and a preliminary conservation assessment of Vulnerable is suggested using the IUCN Red List. Finally, a key to north-eastern Queensland Pandanus species is also provided.