Trypanosoma brucei, a pathogen of human and domestic animals, is an early evolved parasitic protozoan with a complex life cycle. Most genes of this parasite are post-transcriptionally regulated. However, the mechanisms and the molecules involved remain largely unknown. We have deep-sequenced the small RNAs of two life stages of this parasite—the bloodstream form and the procyclic form. Our results show that the small RNAs of T. brucei could derive from multiple sources, including NATs (natural antisense transcripts), tRNAs, and rRNAs. Most of these small RNAs in the two stages were found to share uniform characteristics. However, our results demonstrate that their variety and expression show significant differences between different stages, indicating possible functional differentiation. Dicer-knockdown evidence further proved that some of the small interfering RNAs (siRNAs) could regulate the expression of genes. Based on the genome-wide analysis of the small RNAs in the two stages of T. brucei, our results not only provide evidence to study their differentiation but also shed light on questions regarding the origins and evolution of small RNA-based mechanisms in early eukaryotes.