Staphylininae is the third largest subfamily of the enormous family Staphylinidae. Monophyly of Staphylininae and its sister relationship to the subfamily Paederinae have been broadly accepted according to both conventional morphology- and molecular-based phylogenies until the last three years. Recent molecular phylogenies rejected monophyly of Staphylininae and regarded Paederinae as a clade within it. This paper re-evaluates the recent molecular work, aiming to clarify the relationship between Staphylininae and Paederinae and resolve intertribal relationships within Staphylininae. Based on a new six-gene data set (5707 bp) for 92 taxa including Oxyporinae (outgroup), representatives of Paederinae, and members of all extant tribes of Staphylininae from published DNA data in GenBank, we generated a well-resolved phylogeny of Staphylininae with all deep nodes (intertribal relationships) strongly supported, and reassert the hypothesis that Staphylininae is monophyletic and indeed the sister group to Paederinae using both Bayesian and maximum likelihood inference. Additionally, our study is a case-study to show that both outgroup selection and completeness of nucleotide data can influence the outcome of a molecular phylogeny. With an increasing number of staphylinid fossils being discovered, the robust phylogeny of Staphylininae inferred by our research will provide a good framework for understanding the early evolution of this group.