A cladistic analysis of 87 morphological and life history characters of medusozoan cnidarians, rooted with Anthozoa, results in the phylogenetic hypothesis (Anthozoa (Hydrozoa (Scyphozoa (Staurozoa, Cubozoa)). Staurozoa is a new class of Cnidaria consisting of Stauromedusae and the fossil group Conulatae. Scyphozoa is redefined as including those medusozoans characterized by strobilation and ephyrae (Coronatae, Semaeostomeae, and Rhizostomeae). Within Hydrozoa, Limnomedusae is identified as either the earliest diverging hydrozoan lineage or as the basal group of either Trachylina (Actinulida (Trachymedusae (Narcomedusae, Laingiomedusae))) or Hydroidolina (Leptothecata (Siphonophorae, Anthoathecata)). Cladistic results are highly congruent with recently published phylogenetic analyses based on 18S molecular characters. We propose a phylogenetic classification of Medusozoa that is consistent with phylogenetic hypotheses based on our cladistic results, as well as those derived from 18S analyses. Optimization of the characters presented in this analysis are used to discuss evolutionary scenarios. The ancestral cnidarian probably had a sessile biradial polyp as an adult form. The medusa is inferred to be a synapomorphy of Medusozoa. However, the ancestral process (metamorphosis of the apical region of the polyp or lateral budding involving an entocodon) could not be inferred unequivocally. Similarly, character states for sense organs and nervous systems could not be inferred for the ancestral medusoid of Medusozoa.