Resolving the phylogenetic tree of eukaryotes is an ongoing challenge for evolutionary biologists. One of the most intriguing questions is the phylogenetic status of Excavata, a group that is well supported by morphological evidence, yet usually not recovered as a clade in molecular phylogenies. The most problematic group of excavates are diplomonads (e.g., Giardia), which tend to have very highly divergent gene sequences, making any phylogenetic analyses that include these protists very susceptible to long branch attraction artifact. This thesis first explores which organisms are most closely related to diplomonads. Phylogenies of three marker genes demonstrate that enteromonads, formerly considered a possible sister group to diplomonads, are a polyphyletic group within diplomonads, suggesting complex evolution of cell morphology in this lineage. However, a large diversity of Carpediemonas-like organisms (CLOs) was discovered from marine/saline samples. Most of the major clades of CLOs had not been detected by previous environmental PCR studies. SSU rRNA gene phylogenies show that CLOs form a series of relatively short branches at the base of diplomonads. Phylogenomic analysis of eukaryotes (161 genes), incorporating EST data from 5 excavates, including 3 CLOs, shows that the non-monophyly of Excavata in phylogenomic studies is likely caused by long branch attraction artifact, since most of the methods used to suppress long branch attraction significantly weaken support for this topology. Furthermore, the shorter-branching CLOs represent valuable replacements for the long branching diplomonads; we recovered a robustly supported monophyletic Excavata, when long branches, including diplomonads (and parabasalids), were removed from the analysis. Subsequently, comparative analysis of the putative proteomes of three CLO isolates, the retortamonad Chilomastix, diplomonads and parabasalids was performed. Several putative evolutionary steps leading to the extremely reduced mitochondrial organelle of diplomonads were derived through the comparative analysis of predicted organellar proteomes. This thesis shows the importance of taxon sampling for inferring deep eukaryotic evolution. The more robust understanding of the phylogeny of Excavata, especially diplomonads and parabasalids, and the new availability of a number of deep branching relatives of diplomonads, provide a framework for comparative analyses exploring the evolution of anaerobic organelles or parasitism.