The Plasmodium parasites that cause malaria represent a branch of eukaryotic life that has been committed to an intracellular parasitic lifecycle for as much as a billion years. In this time they have evolved a highly specialised and divergent biology to accommodate a complex lifecycle spanning multiple host cell types across insect and vertebrate hosts. Despite their place as one of the most important human pathogens, much of this biology remains poorly understood. For example, a third of protein-coding Plasmodium genes lack any form of functional annotation, a further third are only putatively annotated on the basis of often limited homology to characterised proteins in other species. Because of this, existing interventions to treat malaria and to control its spread share a limited range of molecular targets, and are increasingly threatened by the emergence of resistance. To address this lack of knowledge, we are applying Protein Correlation Profiling (PCP) and Cross-Linking Mass Spectrometry (XLMS) to P. falciparum, with the goal of establishing a comprehensive map of protein-protein interactions in this species. PCP and XLMS have recently emerged as highly complementary approaches to the study of protein interactions at proteome scale, but they have not been widely applied together, or outside of model organisms. We have developed new machine-learning protocols to enable the integration of our PCP and XLMS datasets with existing data, resulting in a complexome that currently covers almost half of the observable P. falciparum proteome. Our complexome confirms the presence of a range of conserved eukaryotic protein complexes, including several that have not previously been experimentally characterised in Plasmodium. We also identify Plasmodium-specific complexes, as well as conserved eukaryotic processes that appear to be divergent in Plasmodium. For example, we illuminate the unusual composition of the P. falciparum CMG helicase that initiates DNA replication in eukaryotes and archaea. Work is ongoing to further validate and expand the P. falciparum complexome, and to exploit its insights to better understand parasite biology and to identify new therapeutic targets.