Recent work leading to new insights into the molecular architecture underlying complex cellular phenotypes enables researchers to investigate evolutionary processes in unprecedented detail. Protein interaction network data, which are now available for an increasing number of species, promise new insights and there have been many recent studies investigating evolutionary aspects of these interaction networks, from mathematical studies of growing networks to detailed phylogenetic surveys of proteins in their interaction network context. Here, we review the spectrum of such approaches, and assess issues associated with analyzing such data from an evolutionary perspective. Currently, such analyses are statistically challenging, but could link present initiatives in systems biology with results and methodologies that have developed in evolutionary biology over the past 60 years.