An insertion of one or two amino acids at the monomer-monomer junctions of polyubiquitin is a distinct and highly conserved molecular character that is shared by two very diverse clades of microeukaryotes, the Cercozoa and the Foraminifera. It has been suggested that an insertion consisting of one amino acid, like that found in foraminiferans and some cercozoans, represents an ancestral state, and an insertion consisting of two amino acids represents a derived state. However, the limited number of cercozoan taxa examined so far limits inferences about the number and frequency of state changes associated with this character over deep evolutionary time. Cercozoa include a very diverse assemblage of mainly uncultivated amoeboflagellates, and their tenuous phylogenetic interrelationships have been based largely on small subunit (SSU) rDNA sequences. Because concatenated datasets consisting of both SSU and large subunit (LSU) rDNA sequences have been shown to more robustly recover the phylogenetic relationships of other major groups of eukaryotes, we employed a similar approach for the Cercozoa. In order to reconstruct the evolutionary history of this group, we amplified twelve LSU rDNAs, three SSU rDNAs, and seven polyubiquitin sequences from several different cercozoans, especially uncultured taxa isolated from marine benthic habitats. The distribution of single amino acid insertions and double amino acid insertions on the phylogenetic trees inferred from the concatenated dataset indicates that the gain and loss of amino acid residues between polyubiquitin monomers occurred several times independently. Nonetheless, all of the cercozoans we examined possessed at least one amino acid insertion between the polyubiquitin monomers, which reinforced the significance of this feature as a molecular signature for identifying members of the Cercozoa and the Foraminifera. Our study also showed that analyses combining both SSU and LSU rDNA sequences leads to improved phylogenetic resolution and statistical support for deeper branches within the Cercozoa.