Arsenate and phosphate are abundant on Earth and have striking similarities: nearly identical pK(a) values, similarly charged oxygen atoms, and thermochemical radii that differ by only 4% (ref. 3). Phosphate is indispensable and arsenate is toxic, but this extensive similarity raises the question whether arsenate may substitute for phosphate in certain niches. However, whether it is used or excluded, discriminating phosphate from arsenate is a paramount challenge. Enzymes that utilize phosphate, for example, have the same binding mode and kinetic parameters as arsenate, and the latter's presence therefore decouples metabolism. Can proteins discriminate between these two anions, and how would they do so? In particular, cellular phosphate uptake systems face a challenge in arsenate-rich environments. Here we describe a molecular mechanism for this process. We examined the periplasmic phosphate-binding proteins (PBPs) of the ABC-type transport system that mediates phosphate uptake into bacterial cells, including two PBPs from the arsenate-rich Mono Lake Halomonas strain GFAJ-1. All PBPs tested are capable of discriminating phosphate over arsenate at least 500-fold. The exception is one of the PBPs of GFAJ-1 that shows roughly 4,500-fold discrimination and its gene is highly expressed under phosphate-limiting conditions. Sub-ångström-resolution structures of Pseudomonas fluorescens PBP with both arsenate and phosphate show a unique mode of binding that mediates discrimination. An extensive network of dipole-anion interactions, and of repulsive interactions, results in the 4% larger arsenate distorting a unique low-barrier hydrogen bond. These features enable the phosphate transport system to bind phosphate selectively over arsenate (at least 10(3) excess) even in highly arsenate-rich environments.