Phosphate is one of the most frequently exploited chemical moieties in nature, present in a wide range of naturally occurring and critically important small molecules. Several phosphate group recognition motifs have been found for a few narrow groups of proteins, but for many protein families and folds the mode of phosphate recognition remains unclear. Here, we have analyzed the structures of all fold-representative protein-ligand complexes listed in the FSSP database, regardless of whether the bound ligand included a phosphate group. Based on a phosphate-binding motif that we identified in pyridoxal phosphate binding proteins, we have identified a new anion-binding structural motif, CalphaNN, common to 104 fold-representative protein structures that belong to 62 different folds, of which 86% of the fold-representative structures (51 folds) bind phosphate or lone sulfate ions. This motif leads to a precise mode for phosphate group recognition forming a structure where atoms of the phosphate group occupy the most favorable stabilizing positions. The anion-binding CalphaNN motif is based only on main-chain atoms from three adjacent residues, has a conservative betaalphaalpha or betaalphabeta geometry, and recognizes the free phosphate (sulfate) ion as well as one or more phosphate groups in nucleotides and in a variety of cofactors. Moreover, the CalphaNN motif is positioned in functionally important regions of protein structures and often residues of the motif directly participate in the function of the protein.