Cnidarians are the most primitive metazoans, but their evolutionary relationships are poorly understood, although recent studies present several phylogenetic hypotheses. Here, we collected 266 complete cnidarian mitochondrial genomes and re-evaluated the phylogenetic relationships between the major lineages. We described the gene rearrangement patterns of Cnidaria. Anthozoans had significantly greater mitochondrial genome size and lower A + T content than Medusozoans. Most of the protein-coding genes in Anthozoans such as COX 1-3, ATP6, and CYTB displayed a faster rate of evolution based on selection analysis. There were 19 distinct patterns of mitochondrial gene order, including 16 unique gene orders in Anthozoans and 3 mtDNA gene orders pattern in Medusozoans, were identified among cnidarians. The gene order arrangement suggested that a linearized mtDNA structure may be more conducive to Medusozoan mtDNA stability. Based on phylogenetic analyses, the monophyly of the Anthozoa was strongly supported compared to previous mitochondrial genome-based analyses rather than octocorals forming a sister group relationship with medusozoans. In addition, Staurozoa were more closely related to Anthozoa than to Medusozoans. In conclusion, these results largely support the traditional phylogenetic view of the relationships of cnidarians and provide new insights into the evolutionary processes for studying the most ancient animal radiations.