Dynamic protein phosphorylation constitutes a fundamental regulatory mechanism in all organisms. Phosphoprotein phosphatase 4 (PP4) is a conserved and essential nuclear serine and threonine phosphatase. Despite the importance of PP4, general principles of substrate selection are unknown, hampering the study of signal regulation by this phosphatase. Here, we identify and thoroughly characterize a general PP4 consensus-binding motif, the FxxP motif. X-ray crystallography studies reveal that FxxP motifs bind to a conserved pocket in the PP4 regulatory subunit PPP4R3. Systems-wide in silico searches integrated with proteomic analysis of PP4 interacting proteins allow us to identify numerous FxxP motifs in proteins controlling a range of fundamental cellular processes. We identify an FxxP motif in the cohesin release factor WAPL and show that this regulates WAPL phosphorylation status and is required for efficient cohesin release. Collectively our work uncovers basic principles of PP4 specificity with broad implications for understanding phosphorylation-mediated signaling in cells.