The infraorder Anomura consists of a morphologically and ecologically heterogeneous group of decapod crustaceans, and has attracted interest from taxonomists for decades attempting to find some order out of the seemingly chaotic diversity within the group. Species-level diversity within the Anomura runs the gamut from the "hairy" spindly-legged yeti crab found in deep-sea hydrothermal vent environments to the largest known terrestrial invertebrate, the robust coconut or robber crab. Owing to a well-developed capacity for parallel evolution, as evidenced by the occurrence of multiple independent carcinization events, Anomura has long tested the patience and skill of both taxonomists attempting to find order, and phylogeneticists trying to establish stable hypotheses of evolutionary inter-relationships. In this study, we performed genome skimming to recover the mitogenome sequences of 12 anomuran species including the world's largest extant invertebrate, the robber crab (Birgus latro), thereby over doubling these resources for this group, together with 8 new brachyuran mitogenomes. Maximum-likelihood (ML) and Bayesian-inferred (BI) phylogenetic reconstructions based on amino acid sequences from mitogenome protein-coding genes provided strong support for the monophyly of the Anomura and Brachyura and their sister relationship, consistent with previous studies. The majority of relationships within families were supported and were largely consistent with current taxonomic classifications, whereas many relationships at higher taxonomic levels were unresolved. Nevertheless, we have strong support for a polyphyletic Paguroidea and recovered a well-supported clade of a subset of paguroids (Diogenidae + Coenobitidae) basal to all other anomurans, though this requires further testing with greater taxonomic sampling. We also introduce a new feature to the MitoPhAST bioinformatics pipeline (https://github.com/mht85/MitoPhAST) that enables the extraction of mitochondrial gene order (MGO) information directly from GenBank files and clusters groups based on common MGOs. Using this tool, we compared MGOs across the Anomura and Brachyura, identifying Anomura as a taxonomic "hot spot" with high variability in MGOs among congeneric species from multiple families while noting the broad association of highly-rearranged MGOs with several anomuran lineages inhabiting extreme niches. We also demonstrate the value of MGOs as a source of novel synapomorphies for independently reinforcing tree-based relationships and for shedding light on relationships among challenging groups such as the Aegloidea and Lomisoidea that were unresolved in phylogenetic reconstructions. Overall, this study contributes a substantial amount of new genetic material for Anomura and attempts to further resolve anomuran evolutionary relationships where possible based on a combination of sequence and MGO information. The new feature in MitoPhAST adds to the relatively limited number of bioinformatics tools available for MGO analyses, which can be utilized widely across animal groups.