Eukaryotes have evolved elaborate splicing mechanisms to remove introns that would otherwise destroy the protein-coding capacity of genes. Nuclear premRNA splicing requires sequence motifs in the intron and is mediated by a ribonucleoprotein complex, the spliceosome. Here we demonstrate the presence of a splicing apparatus in the protist Trichomonas vaginalis and show that RNA motifs found in yeast and metazoan introns are required for splicing. We also describe the first introns in this deep-branching lineage. The positions of these introns are often conserved in orthologous genes, indicating they were present in a common ancestor of trichomonads, yeast, and metazoa. All examined T. vaginalis introns have a highly conserved 12-nt 3-prime splice-site motif that encompasses the branch point and is necessary for splicing. This motif is also found in the only described intron in a gene from another deep-branching eukaryote, Giardia intestinalis. These studies demonstrate the conservation of intron splicing signals across large evolutionary distances, reveal unexpected motif conservation in deep-branching lineages that suggest a simplified mechanism of splicing in primitive unicellular eukaryotes, and support the presence of introns in the earliest eukaryote.