Post-translational modification of proteins by ubiquitin or ubiquitin-like polypeptides such as Nedd8 controls cellular functions including protein degradation, the cell cycle and transcription. Here we have used an activity-based chemical probe that covalently labels ubiquitin hydrolases. We identify four such enzymes from Toxoplasma gondii by mass spectrometry. The homologue of mammalian UCHL3 was cloned from both T. gondii and Plasmodium falciparum and we show that both enzymes possess deubiquitinating as well as deNeddylating activity. A phylogenetic analysis of the UCHL3 amino acid sequences from several eukaryotes suggests that dual specificity for ubiquitin and Nedd8 was present in the ancestral eukaryotic UCHL3 and has been conserved throughout evolution. Finally, the structural characterization of UCHL3 from T. gondii shows a unique insertion at the surface of this enzyme, which may be involved in novel interactions with other proteins. The characterization of these apicomplexan UCHL3s adds to our understanding of the ubiquitin and Nedd8 pathways in these parasites.