Mekongomantis quinquespinosa gen. et sp. nov., a new Mantidae genus and species is described based on specimens from two localities—Lam Vien plateau in Vietnam and the environments of Umphang, Thailand. The new genus has five posteroventral spines on the forefemur, a feature previously unknown in any Mantidae (sensu stricto) genus. The rest of external morphology is similar to Tenodera Burmeister, 1838 and Mantis Linnaeus, 1758, while the characters of the male genitalia place the species more closely to Hierodula Burmeister, 1838 and Camelomantis Giglio-Tos, 1917. The discovery of such a large (>70 mm) genus level taxon exemplifies the poorly studied diversity of Mantodea in the rapidly deteriorating Greater Mekong area. To ease identification, we also provide a key to the Mantidae of South-East Asia.