The topology of the proteome map revealed by recent large-scale hybridization methods has shown that the distribution of protein–protein interactions is highly heterogeneous, with many proteins having few edges while a few of them are heavily connected. This particular topology is shared by other cellular networks, such as metabolic pathways, and it has been suggested to be responsible for the high mutational homeostasis displayed by the genome of some organisms. In this paper we explore a recent model of proteome evolution that has been shown to reproduce many of the features displayed by its real counterparts. The model is based on gene duplication plus re-wiring of the newly created genes. The statistical features displayed by the proteome of well-known organisms are reproduced and suggest that the overall topology of the protein maps naturally emerges from the two leading mechanisms considered by the model.