Extensive bioinformatics analysis suggests that the stability and function of protein complexes are maintained throughout evolution by coordinated changes (co-evolution) of complex subunits. Yet, relatively little is known regarding the actual dynamics of such processes and the functional implications of co-evolution within protein complexes, since most of the bioinformatics predictions were not analyzed experimentally. Here, we describe a systematic experimental approach that allows a step-by-step observation of the co-evolution process in protein complexes. The exosome complex, an essential complex exhibiting a 3'→5' RNA degradation activity, served as a model system. In this study, we show that exosome subunits diverged very early during fungal evolution. Interestingly, we found that despite significant differences in conservation between Rrp41 and Mtr3 both subunits exhibit similar divergence pattern and co-evolutionary behavior through fungi evolution. Activity analysis of mutated exosomes exposes another layer of co-evolution between the core subunits and RNA substrates. Overall, our approach allows the experimental analysis of co-evolution within protein complexes and together with bioinformatics analysis can significantly deepen our understanding of the evolution of these complexes.