We have conducted a protein interaction study of components within a specific sub-compartment of a eukaryotic flagellum. The trypanosome flagellum contains a para-crystalline extra-axonemal structure termed the paraflagellar rod (PFR) with around forty identified components. We have used a Gateway cloning approach coupled with yeast two-hybrid, RNAi and 2D DiGE to define a protein-protein interaction network taking place in this structure. We define two clusters of interactions; the first being characterised by two proteins with a shared domain which is not sufficient for maintaining the interaction. The other cohort is populated by eight proteins, a number of which possess a PFR domain and sub-populations of this network exhibit dependency relationships. Finally, we provide clues as to the structural organisation of the PFR at the molecular level. This multi-strand approach shows that protein interactome data can be generated for insoluble protein complexes.