Staurozoan classification is highly subjective, based on phylogeny-free inferences, and suborders, families, and genera are commonly defined by homoplasies. Additionally, many characters used in the taxonomy of the group have ontogenetic and intraspecific variation, and demand new and consistent assessments to establish their correct homologies. Consequently, Staurozoa is in need of a thorough systematic revision. The aim of this study is to propose a comprehensive phylogenetic hypothesis for Staurozoa, providing the first phylogenetic classification for the group. According to our working hypothesis based on a combined set of molecular data (mitochondrial markers COI and 16S, and nuclear markers ITS, 18S, and 28S), the traditional suborders Cleistocarpida (animals with claustrum) and Eleutherocarpida (animals without claustrum) are not monophyletic. Instead, our results show that staurozoans are divided into two groups, herein named Amyostaurida and Myostaurida, which can be distinguished by the absence/presence of interradial longitudinal muscles in the peduncle, respectively. We propose a taxonomic revision at the family and genus levels that preserves the monophyly of taxa. We provide a key for staurozoan genera and discuss the evolution of the main characters used in staurozoan taxonomy.