The class Clostridia in the phylum Firmicutes includes a very heterogeneous assemblage of bacteria. Their evolutionary relationships are not well established; revisions of their phylogenetic placements based on comparative studies of 16S rRNA gene sequences are in progress as genome sequence information accumulates. In this work, phylogenetic trees were reconstructed based on 21 concatenated ribosomal protein sequences using Bayesian and maximum-likelihood methods. Both trees consistently indicate that the Halanaerobiales is a deeply branching order among the class Clostridia. The rest of the Clostridia species are grouped into 10 monophyletic clusters, most of which are comprised of two or three orders and families according to the current Clostridial taxonomy. The maximum-likelihood tree placed Coprothermobacter proteolyticus and Thermodesulfobium narugense in the class Clostridia in accordance with the current taxonomy, in which these two bacteria are assigned to the family Thermodesulfobiaceae. However, the Bayesian tree placed these two bacteria at the boundary between the Firmicutes and Actinobacteria. A gene arrangement that is present uniquely in the Firmicutes species was identified. Both Coprothermobacter proteolyticus and Thermodesulfobium narugense do not have this arrangement characteristic of the Firmicutes. On the basis of the Bayesian tree and gene arrangement comparison, it is suggested that Coprothermobacter proteolyticus and Thermodesulfobium narugense should be placed outside the phylum Firmicutes.