It has become evident over the past few years that many complex cellular processes, including control of the cell cycle and ubiquitin-dependent proteolysis, are carried out by sophisticated multisubunit protein machines that are dynamic in abundance, post-translational modification state, and composition. To understand better the nature of the macromolecular assemblages that carry out the cell cycle and ubiquitin-dependent proteolysis, we have used mass spectrometry extensively over the past few years to characterize both the composition of various protein complexes and the modification states of their subunits. In this article we review some of our recent efforts, and describe a promising new approach for using mass spectrometry to dissect protein interaction networks.