All cellular functions depend on the concerted action of multiple proteins organized in complex networks. To understand how selection acts on protein networks, we used the yeast mating receptor Ste2, a pheromone-activated G protein-coupled receptor, as a model system. In Saccharomyces cerevisiae, Ste2 is a hub in a network of interactions controlling both signal transduction and signal suppression. Through laboratory evolution, we obtained 21 mutant receptors sensitive to the pheromone of a related yeast species and investigated the molecular mechanisms behind this newfound sensitivity. While some mutants show enhanced binding affinity to the foreign pheromone, others only display weakened interactions with the network's negative regulators. Importantly, the latter changes have a limited impact on overall pathway regulation, despite their considerable effect on sensitivity. Our results demonstrate that a new receptor-ligand pair can evolve through network-altering mutations independently of receptor-ligand binding, and suggest a potential role for such mutations in disease.