Recent phylogenetic analyses based on different molecular markers have revealed the existence of the Cercozoa, a group of protists including such morphologically diverse taxa as the cercomonad flagellates, the euglyphid testate filose amoebae, the chloroplast-bearing chlorarachniophytes, and the plasmodiophorid plant pathogens. Molecular data also indicate a close relationship between Cercozoa and Foraminifera (Granuloreticulosea). Little is known, however, about the origin of both groups and their phylogenetic relationships. Here we present the complete small-subunit ribosomal RNA (SSU rRNA) sequence of Gymnophrys cometa, formerly included in the athalamid Granuloreticulosea, as well as that of the test-bearing filose amoeba Lecythium sp. Our study shows that the two organisms clearly belong to the Cercozoa, and indicates that Gymnophrys is not closely related to Foraminifera, supporting the view that Granuloreticulosea sensu lato do not form a natural assemblage. Phylogenetic analyses including most available SSU rRNA sequences from Cercozoa suggest that a rigid, external cell envelope appeared several times independently during the evolution of the group. Furthermore, our results bring additional evidence for the wide morphological variety among Cercozoa, which now also include protists bearing granular pseudopodia and exhibiting mitochondria with flattened cristae.