Class Demospongiae (phylum Porifera) encompasses most of sponges' morphological and species diversity. It also represents one of the most challenging and understudied groups in animal phylogenetics, with many higher-level relationships still being unresolved. Among the unanswered questions are the most fundamental, including those about the monophyly of the Demospongiae and the relationships among the 14 recognized orders within the class. The lack of resolved phylogeny hampers progress in studies of demosponge biology, evolution and biodiversity and may interfere with the efficient conservation and economic use of this group. We addressed the question of demosponge relationships using mitochondrial genomic data. We assembled a mitochondrial genomic dataset comprising all orders of demosponges that includes 17 new and five previously published complete demosponge mitochondrial genomes. To test for the congruence between mtDNA-based and nuclear rRNA-based phylogenies, we also determined and analyzed 18S rRNA sequences for the same set of species. Our results provide strong support for five major clades within the Demospongiae: Homoscleromorpha=G0 (order Homosclerophorida), Keratosa=G1 (orders Dendroceratida, Dictyoceratida, and Verticillitida), Myxospongiae=G2 (orders Chondrosida, Halisarcida, and Verongida), marine Haplosclerida=G3 and the rest of demosponges=G4 (orders Agelasida, Astrophorida, Hadromerida, Halichondrida, Poecilosclerida, Spirophorida, and freshwater Haploscerida), and for the (G0((G1+G2)(G3+G4)) relationships among these clades. Conversely, mitochondrial genomic data do not support the monophylies of traditional subclasses Ceractinomorpha and Tetractinomorpha as well as several currently recognized orders of demosponges. Furthermore, we demonstrate that mitochondrial gene arrangements can also be informative for the inference of order-level demosponge relationships and propose a modified method for the analysis of gene order data that works well when translocation of tRNA genes are more frequent than other rearrangements.