All species from the phylum Thermotogae, class Thermotogae, are currently part of a single family, Thermotogaceae. Using genomic data from 17 Thermotogae species, detailed phylogenetic and comparative genomic analyses were carried out to understand their evolutionary relationships and identify molecular markers that are indicative of species relationships within the phylum. In the 16S rRNA gene tree and phylogenetic trees based upon two different large sets of proteins, members of the phylum Thermotogae formed a number of well-resolved clades. Character compatibility analysis on the protein sequence data also recovered a single largest clique that exhibited similar topology to the protein trees and where all nodes were supported by multiple compatible characters. Comparative genomic analyses have identified 85 molecular markers, in the form of conserved signature indels (CSIs), which are specific for different observed clades of Thermotogae at multiple phylogenetic depths. Eleven of these CSIs were specific for the phylum Thermotogae whereas nine others supported a clade comprising of the genera Thermotoga, Thermosipho and Fervidobacterium. Ten other CSIs provided evidence that the genera Thermosipho and Fervidobacterium shared a common ancestor exclusive of the other Thermotogae and four and eight CSIs in other proteins were specific for the genera Thermosipho and Fervidobacterium, respectively. Two other deep branching clades, one consisting of the genera Kosmotoga and Mesotoga and the other comprising of the genera Petrotoga and Marinitoga, were also supported by multiple CSIs. Based upon the consistent branching of the Thermotogae species using different phylogenetic approaches, and numerous identified CSIs supporting the distinctness of different clades, it is proposed that the class Thermotogae should be divided into three orders (Thermotogales, Kosmotogales ord. nov. and Petrotogales ord. nov.) containing four families (Thermotogaceae, Fervidobacteriaceae fam. nov., Kosmotogaceae fam. nov. and Petrotogaceae fam. nov.). Additionally, the results of our phylogenetic/compatibility studies along with the species distribution patterns of 22 identified CSIs, provide compelling evidence that the current genus Thermotoga is comprised of two evolutionary distinct groups and that it should be divided into two genera. It is proposed that the emended genus Thermotoga should retain only the species Thermotoga maritima, Tt. neapolitana, Tt. petrophila, Tt. naphthophila, Thermotoga sp. EMP, Thermotoga sp. A7A and Thermotoga sp. RQ2 while the other Thermotoga species (viz. Tt. lettingae, Tt. thermarum, Tt. elfii, Tt. subterranean and Tt. hypogea) be transferred to a new genus, Pseudothermotoga gen. nov.