The Parabasala are a primitive group of protists divided into two classes: the trichomonads and the hypermastigids. Until recently, phylogeny and taxonomy of parabasalids were mainly based on the comparative analysis of morphological characters primarily linked to the development of their cytoskeleton. Recent use of molecular markers, such as small subunit (SSU) rRNA has led to now insights into the systematics of the Parabasala and other groups of prolists. An updated phylogeny based on SSU rRNA is provided and compared to that inferred from ultrastructural data. The SSU rRNA phylogeny contradicts the dogma equating simple characters with pumitive characters. Hypermastigids, possessing a hyperdeveloped cytoskeleton, exhibit the most basal emergence in the parabasalid lineage. Other observations emerge from the SSU rRNA analysis, such as the secondary loss of some cytoskeleton structures in all representatives of the Monocercomonadidae, the existence of secondarily free living taxa (reversibility of parasitism) and the evidence against the co-evolution of the endobiotic parabasalids and their animal hosts. According to phylogenies based on SSU rRNA, all the trichomonad families are not monophyletic groups, putting into question the validity of current taxonomic assignments. The precise branching order of some taxa remains unclear, but this issue can possibly be addressed by the molecular analysis of additional parabasalids. The goal of such additional analyses would be to propose, in a near future, a revision of the taxonomy of this group of protists that takes into account both molecular and morphological data.