It is now clear that the genomes of many organisms encode thousands of large and small non-coding (nc)RNAs. However, relative to the discovery of ncRNAs the functions and mechanisms of ncRNAs remain disproportionately understood. One intriguing observation is that many ncRNAs are found to be associated with protein complexes including those involved in transcription regulation, post-transcriptional silencing, and epigentic regulation. These observations suggest that the functions and mechanisms of many of these ncRNAs may depend on their interactions with various protein complexes within the cell. In this review we discuss well known examples as well as newly emerging evidence of a widespread RNA-protein interactions in distinct biological processes in a wide range of organisms, and highlight the importance of developing new technologies to dissect these interactions. Finally, we propose that mis-regulation of ncRNAs interactions with their protein partners may contribute to human disease, and open up a novel approach to therapeutic interventions.