The availability of high-throughput methods to detect protein interactions made construction of comprehensive protein interaction networks for several important model organisms possible. Many studies have since focused on uncovering the structural principles of these networks and relating these structures to biological processes. On a global scale, there are striking similarities in the structure of different protein interaction networks, even when distantly related species, such as the yeast Saccharomyces cerevisiae and the fruit fly Drosophila melanogaster, are compared. However, there is also considerable variance in network structures caused by the gain and loss of genes and mutations which alter the interaction behavior of the encoded proteins. Here, we focus on the current state of knowledge on the structure of protein interaction networks and the evolutionary processes that shaped these structures.