Ribonucleoprotein complexes are composed of RNA, RNA-dependent proteins (RDPs) and RNA-binding proteins (RBPs), and play fundamental roles in RNA regulation. However, in the human malaria parasite, Plasmodium falciparum, identification and characterization of these proteins are particularly limited. In this study, we use an unbiased proteome-wide approach, called R-DeeP, a method based on sucrose density gradient ultracentrifugation, to identify RDPs. Quantitative analysis by mass spectrometry identifies 898 RDPs, including 545 proteins not yet associated with RNA. Results are further validated using a combination of computational and molecular approaches. Overall, this method provides the first snapshot of the Plasmodium protein-protein interaction network in the presence and absence of RNA. R-DeeP also helps to reconstruct Plasmodium multiprotein complexes based on co-segregation and deciphers their RNA-dependence. One RDP candidate, PF3D7_0823200, is functionally characterized and validated as a true RBP. Using enhanced crosslinking and immunoprecipitation followed by high-throughput sequencing (eCLIP-seq), we demonstrate that this protein interacts with various Plasmodium non-coding transcripts, including the var genes and ap2 transcription factors.