Discovery of adults and a larva of Natalignathus, a new South African endemic genus, and examination of previously undescribed larvae of Atanygnathus Jakobson shed light on the phylogenetic relationships of the puzzling rove beetle subtribe Tanygnathinina (Staphylinidae : Staphylininae : Staphylinini). Based on plesiomorphic states for many characters of Natalignathus, gen. nov., inferred on the basis of comparison of the new genus with Atanygnathus, various Quediina and other Staphylinini, Natalignathus can be considered either a relatively plesiomorphy-rich member of Tanygnathinina, or a derived genus of Quediina, essentially linking these two subtribes together. Based on morphological and distributional data, it is preliminarily assumed that Atanygnathus evolved from some lineage of southern Quediina, which currently are very poorly known. Comparative study of the adults of Natalignathus and Atanygnathus allows correction of earlier misinterpretations of the structure of the aedeagus and head capsule ridges of Atanygnathus. Detailed morphological descriptions are provided for adults and a larva of Natalignathus and for the larvae of two species of Atanygnathus, A. bicolor (Casey) and A. sp. 1. Special appendages of unknown function are present on the mesothoracic spiracles of the examined larvae of Atanygnathus. No similar structures are known in any other group of Staphylinidae or Coleoptera. Based on the new findings, a review of the state of knowledge of the subtribes Quediina and Tanygnathinina and an updated diagnosis of the latter are provided.