Many cellular pathways are regulated by the competing activity of protein kinases and phosphatases. The recent identification of arginine phosphorylation as a protein modification in bacteria prompted us to analyze the molecular basis of targeting phosphoarginine. In this work, we characterize an annotated tyrosine phosphatase, YwlE, that counteracts the protein arginine kinase McsB. Strikingly, structural studies of YwlE reaction intermediates provide a direct view on a captured arginine residue. Together with biochemical data, the crystal structures depict the evolution of a highly specific phospho-arginine phosphatase, with the use of a size-and-polarity filter for distinguishing phosphorylated arginine from other phosphorylated side chains. To confirm the proposed mechanism, we performed bioinformatic searches for phosphatases, employing a similar selectivity filter, and identified a protein in Drosophila melanogaster exhibiting robust arginine phosphatase activity. In sum, our findings uncover the molecular framework for specific targeting of phospho-arginine and suggest that protein arginine (de) phosphorylation may be relevant in eukaryotes.