Cadmium (Cd), one of the heavy metal pollution sources, has a strong impact on crop growth and development, yield formation, and food safety. In this work, we perform the first comprehensive study on the molecular mechanisms of wheat (Triticum aestivum L.) selenium-binding protein-A (TaSBP-A) that is involved in Cd-tolerance. As a cytoplasm protein, TaSBP-A was highly conservative in plants, but showed a high expression in plant roots; moreover, both transcription and translation expression levels were highly induced by Cd stress. TaSBP-A overexpression in yeast, Arabidopsis and wheat protoplasts enhanced Cd-tolerance via free Cd2+ accumulation and detoxification. In vitro Cd2+ binding assay combined with a thermodynamics survey by isothermal titration calorimetry as well as secondary structure analysis by circular dichroism showed that the CXXC motif in TaSBP-A was a major Cd-binding site that played important roles in the detoxification under Cd stress via its interaction with free Cd2+. Our results provide new insights into the molecular mechanism of plant Cd-tolerance as well as into the candidate gene for improving crop heavy metal resistance.