Most cellular processes are conducted by multi-protein complexes. However, little is known about how these complexes are assembled. In particular, it is not known if they are formed while one or more members of the complexes are being translated (cotranslational assembly). We took a genomic approach to address this question, by systematically identifying mRNAs associated with specific proteins. In a sample of 31 proteins from Schizosaccharomyces pombe that did not contain RNA-binding domains, we found that ∼38% copurify with mRNAs that encode interacting proteins. For example, the cyclin-dependent kinase Cdc2p associates with the rum1 and cdc18 mRNAs, which encode, respectively, an inhibitor of Cdc2p kinase activity and an essential regulator of DNA replication. Both proteins interact with Cdc2p and are key cell cycle regulators. We obtained analogous results with proteins with different structures and cellular functions (kinesins, protein kinases, transcription factors, proteasome components, etc.). We showed that copurification of a bait protein and of specific mRNAs was dependent on the presence of the proteins encoded by the interacting mRNAs and on polysomal integrity. These results indicate that these observed associations reflect the cotranslational interaction between the bait and the nascent proteins encoded by the interacting mRNAs. Therefore, we show that the cotranslational formation of protein-protein interactions is a widespread phenomenon.