Mitogen-activated protein kinase (MAPK) activation depends on a linear binding motif found in all MAPK kinases (MKK). In addition, the PB1 (Phox and Bem1) domain of MKK5 is required for extracellular signal regulated kinase 5 (ERK5) activation. We present the crystal structure of ERK5 in complex with an MKK5 construct comprised of the PB1 domain and the linear binding motif. We show that ERK5 has distinct protein-protein interaction surfaces compared with ERK2, which is the closest ERK5 paralog. The two MAPKs have characteristically different physiological functions and their distinct protein-protein interaction surface topography enables them to bind different sets of activators and substrates. Structural and biochemical characterization revealed that the MKK5 PB1 domain cooperates with the MAPK binding linear motif to achieve substrate specific binding, and it also enables co-recruitment of the upstream activating enzyme and the downstream substrate into one signaling competent complex. Studies on present day MAPKs and MKKs hint on the way protein kinase networks may evolve. In particular, they suggest how paralogous enzymes with similar catalytic properties could acquire novel signaling roles by merely changing the way they make physical links to other proteins.