MAP kinases regulate essential cellular events, including cell growth, differentiation and inflammation. The solution structure of a complete MAPK-MAPK-regulatory protein complex, p38α-HePTP, was determined, enabling a comprehensive investigation of the molecular basis of specificity and fidelity in MAPK regulation. Structure determination was achieved by combining NMR spectroscopy and small-angle X-ray scattering data with a new ensemble calculation-refinement procedure. We identified 25 residues outside of the HePTP kinase interaction motif necessary for p38α recognition. The complex adopts an extended conformation in solution and rarely samples the conformation necessary for kinase deactivation. Complex formation also does not affect the N-terminal lobe, the activation loop of p38α or the catalytic domain of HePTP. Together, these results show how the downstream tyrosine phosphatase HePTP regulates p38α and provide for fundamentally new insights into MAPK regulation and specificity.