Protein tyrosine phosphatase receptor-type kappa (PTPRK) is a transmembrane receptor that links extracellular homophilic interactions to intracellular catalytic activity. Previously we showed that PTPRK promotes cell-cell adhesion by selectively dephosphorylating several cell junction regulators including the protein Afadin (Fearnley et al., 2019). Here we demonstrate that Afadin is recruited for dephosphorylation by directly binding to the PTPRK D2 pseudophosphatase domain. We mapped this interaction to a putative coiled coil (CC) domain in Afadin that is separated by more than 100 amino acids from the substrate pTyr residue. We identify the residues that define PTP specificity, explaining how Afadin is selectively dephosphorylated by PTPRK yet not by the closely related receptor tyrosine phosphatase PTPRM. Our work demonstrates that PTP substrate specificity can be determined by protein-protein interactions distal to the active site. This explains how PTPRK and other PTPs achieve substrate specificity despite a lack of specific sequence context at the substrate pTyr. Furthermore, by demonstrating that these interactions are phosphorylation-independent and mediated via binding to a non-catalytic domain, we highlight how receptor PTPs could function as intracellular scaffolds in addition to catalyzing protein dephosphorylation.