In trypanosomatids, gene expression is regulated mainly by post-transcriptional mechanisms, which affect mRNA processing, translation and degradation. Currently, our understanding of factors that regulate either mRNA stability or translation is rather limited. We know that often, the regulators are proteins that bind to the 3′-untranslated region; they presumably interact with ribonucleases and translation factors. However, very few such proteins have been characterized in any detail. Here we describe a genome-wide screen to find proteins implicated in post-transcriptional regulation in Trypanosoma brucei. We made a library of random genomic fragments in a plasmid that was designed for expression of proteins fused to an RNA-binding domain, the lambda-N peptide. This was transfected into cells expressing mRNAs encoding a positive or negative selectable marker, and bearing the “boxB” lambda-N recognition element in the 3′-untranslated region. The screen identified about 300 proteins that could be implicated in post-transcriptional mRNA regulation. These included known regulators, degradative enzymes and translation factors, many canonical RNA-binding proteins, and proteins that act via multi-protein complexes. However there were also nearly 150 potential regulators with no previously annotated function, or functions unrelated to mRNA metabolism. Almost 50 novel regulators were shown to bind RNA using a targeted proteome array. The screen also provided fine structure mapping of the hit candidates' functional domains. Our findings not only confirm the key role that RNA-binding proteins play in the regulation of gene expression in trypanosomatids, but also suggest new roles for previously uncharacterized proteins.