We study the mechanisms and patterns of protein evolution. In particular, we are focused on understanding how interacting proteins coevolve to maintain their interactions and how paralogous proteins evolve interaction specificity, avoiding detrimental cross-talk in cells. We use a combination of experimental evolution, phylogenetic analysis, and classical genetics + biochemistry to tackle these problems. Recent efforts have also exploited the power of next-generation sequencing coupled with extremely large, diverse mutant libraries to systematically map the sequence spaces relevant to protein-protein interactions and protein evolution. We apply these approaches mainly to two important and widespread families of proteins in bacteria, two-component signaling proteins and toxin-antitoxin systems.