AbstractMitogen‐activated protein kinase (MAPK) pathways are well conserved in most organisms, from yeast to humans. The principal components of these pathways are MAP kinases whose activity is regulated by phosphorylation, implicating various MAPK protein effectors—in particular, protein phosphatases that inactivate MAPKs by dephosphorylation. The molecular basis of binding specificity of such regulatory phosphatases to MAPKs is poorly understood. To try to pinpoint potential functional regions within the sequences and to help identify new family members, we have applied a multimotif pattern‐recognition approach to characterize two MAPK phosphatase subfamilies (tyrosine‐specific and dual specificity) that are crucial in the regulation of MAPKs. We built “fingerprints” for these two subfamilies that are unique to, and highly discriminatory for, each group of proteins. The fingerprints were used in a genome‐wide screen, identifying more than 80 MAPK phosphatase domains, several of which were in partial sequences or unclassified proteins. We confirmed experimentally that one predicted MAPK phosphatase orthologue in Xenopus binds to ERK1/2, suggesting a role in MAPK signaling and thus supporting our functional predictions. Further analysis, mapping the fingerprints on the three‐dimensional structure of MAPK phosphatases, revealed that some of the fingerprint motifs reside in the N‐terminal noncatalytic regions coinciding with reported MAPK binding sites, while others lie within the catalytic phosphatase domain. These results also suggest the presence of putative allosteric sites in the catalytic region for modulation of protein–protein interactions, and provide a framework for future experimental validation. Proteins 2007. © 2007 Wiley‐Liss, Inc.