The Epsilonproteobacteria is the fifth validly described class of the phylum Proteobacteria, known primarily for clinical relevance and for chemolithotrophy in various terrestrial and marine environments, including deep-sea hydrothermal vents. As 16S rRNA gene repositories have expanded and protein marker analysis become more common, the phylogenetic placement of this class has become less certain. A number of recent analyses of the bacterial tree of life using both 16S rRNA and concatenated marker gene analyses have failed to recover the Epsilonproteobacteria as monophyletic with all other classes of Proteobacteria. In order to address this issue, we investigated the phylogenetic placement of this class in the bacterial domain using 16S and 23S rRNA genes, as well as 120 single-copy marker proteins. Single- and concatenated-marker trees were created using a data set of 4,170 bacterial representatives, including 98 Epsilonproteobacteria. Phylogenies were inferred under a variety of tree building methods, with sequential jackknifing of outgroup phyla to ensure robustness of phylogenetic affiliations under differing combinations of bacterial genomes. Based on the assessment of nearly 300 phylogenetic tree topologies, we conclude that the continued inclusion of Epsilonproteobacteria within the Proteobacteria is not warranted, and that this group should be reassigned to a novel phylum for which we propose the name Epsilonbacteraeota (phyl. nov.). We further recommend the reclassification of the order Desulfurellales (Deltaproteobacteria) to a novel class within this phylum and a number of subordinate changes to ensure consistency with the genome-based phylogeny. Phylogenomic analysis of 658 genomes belonging to the newly proposed Epsilonbacteraeota suggests that the ancestor of this phylum was an autotrophic, motile, thermophilic chemolithotroph that likely assimilated nitrogen from ammonium taken up from the environment or generated from environmental nitrate and nitrite by employing a variety of functional redox modules. The emergence of chemoorganoheterotrophic lifestyles in several Epsilonbacteraeota families is the result of multiple independent losses of various ancestral chemolithoautotrophic pathways. Our proposed reclassification of this group resolves an important anomaly in bacterial systematics and ensures that the taxonomy of Proteobacteria remains robust, specifically as genome-based taxonomies become more common.