Analysis of RNA-protein complexes is central to understanding the molecular circuitry governing cellular processes. In recent years, several proteome-wide studies have been dedicated to the identification of RNA-binding proteins. Here, we describe in detail R-DeeP, an approach built on RNA dependence, defined as the ability of a protein to engage in protein complexes only in the presence of RNA, involving direct or indirect interaction with RNA. This approach provides-for the first time, to our knowledge-quantitative information on the fraction of a protein associated with RNA-protein complexes. R-DeeP is independent of any potentially biased purification procedures. It is based on cellular lysate fractionation by density gradient ultracentrifugation and subsequent analysis by proteome-wide mass spectrometry (MS) or individual western blotting. The comparison of lysates with and without previous RNase treatment enables the identification of differences in the apparent molecular weight and, hence, the size of the complexes. In combination with information from databases of protein-protein complexes, R-DeeP facilitates the computational reconstruction of protein complexes from proteins migrating in the same fraction. In addition, we developed a pipeline for the statistical analysis of the MS dataset to automatically identify RNA-dependent proteins (proteins whose interactome depends on RNA). With this protocol, the individual analysis of proteins of interest by western blotting can be completed within 1-2 weeks. For proteome-wide studies, additional time is needed for the integration of the proteomic and statistical analyses. In the future, R-DeeP can be extended to other fractionation techniques, such as chromatography.