The characterization of heterogeneous multi-component protein complexes, which goes beyond identification of protein subunits, is a challenging task. Here we describe and apply a comprehensive method that combines a mild affinity purification procedure with a multiplexed mass spectrometry approach for the in-depth characterization of the exosome complex from Saccharomyces cerevisiae expressed at physiologically relevant levels. The exosome is an ensemble of primarily 3’->5’ exoribonucleases and plays a major role in RNA metabolism. The complex has been reported to consist of 11 proteins, in molecular weight ranging from 20 to 120 kDa. By using native macromolecular mass spectrometry we measured accurate masses (around 400 kDa) of several (sub)-exosome complexes. Combination of these data with proteolytic peptide LC tandem mass spectrometry using a LTQ-FT-ICR and intact protein LC mass spectrometry provided us with the identity of the different exosome components and (sub)-complexes, including the subunit stoichiometry. We hypothesize that the observed complexes provide information about strong and weak interacting exosome-associated proteins. In our analysis we also identified for the first time phosphorylation sites in seven different exosome subunits. The phosphorylation site in the Rrp4 subunit is fully conserved in the human homologue of Rrp4, which is the only previously reported phosphorylation site in any of the human exosome proteins. The described multiplexed mass spectrometry-based procedure is generic and thus applicable to many different types of cellular molecular machineries, even if they are expressed at endogenous levels.