Stenus is the largest genus of rove beetles and the second largest among animals. Its evolutionary success was associated with the adhesive labial prey-capture apparatus, a unique apomorphy of that genus. Definite Stenus with prey-capture apparatus are known from the Cenozoic fossils, while the age and early evolution of Steninae was hardly ever hypothesized. Our study of several Cretaceous Burmese amber inclusions revealed a stem lineage of Steninae that possibly possesses the Stenus-like prey-capture apparatus. Phylogenetic analysis of extinct and extant taxa of Steninae and putatively allied subfamilies of Staphylinidae with parsimony and Bayesian approaches resolved the Burmese amber lineage as a member of Steninae. It justified the description of a new extinct stenine genus Festenus with two new species, F. robustus and F. gracilis. The Late Cretaceous age of Festenus suggests an early origin of prey-capture apparatus in Steninae that, perhaps, drove the evolution towards the crown Stenus. Our analysis confirmed the well-established sister relationships between Steninae and Euaesthetinae and resolved Scydmaeninae as their next closest relative, the latter having no stable position in recent phylogenetic studies of rove beetles. Close affiliation of Megalopsidiinae, a subfamily often considered as a sister group to Euaesthetinae + Steninae clade, is rejected.