A new flightless genus and species of Lucanidae, Pelekysaegus robustus gen. et sp. nov., is described from New Guinea. The new genus is morphologically allied to Pachistaegus de Lisle, 1967, Tumidaegus Bomans, 1988, Cherasphorus Bomans, 1988 and Microlucanus Bomans & Bartolozzi, 1996, sharing a combination of flightlessness and secondary sexual dimorphism at the elytral apex in males. Based on external morphology, several species previously placed in Gnaphaloryx Burmeister, 1847 are re-evaluated. Gnaphaloryx furfuraceus (de Lisle, 1970) is transferred to Cherasphorus Bomans, and G. pulverosus (Benesh, 1952) and G. stigmatifer de Lisle, 1974 are transferred to Microlucanus Bomans & Bartolozzi; G. pollinosus de Lisle, 1973 is tentatively transferred to Microlucanus Bomans & Bartolozzi. In addition, Pelekysaegus gen. nov., together with Pachistaegus de Lisle, Tumidaegus Bomans, Cherasphorus Bomans, and Microlucanus Bomans & Bartolozzi, is herein placed in the tribe Aegini Huang & Chen based on shared morphological characters. The taxonomic implications of these changes are briefly discussed.