Calcineurin B-like (CBL) proteins represent a unique family of calcium sensors in plant cells. Sensing the calcium signals elicited by a variety of abiotic stresses, CBLs transmit the information to a group of serine/threonine protein kinases (CBL-interacting protein kinases [CIPKs]), which are currently known as the sole targets of the CBL family. Here, we report that the CBL3 member of this family has a novel interaction partner in addition to the CIPK proteins. Extensive yeast two-hybrid screenings with CBL3 as bait identified an interesting Arabidopsis (Arabidopsis thaliana) cDNA clone (named AtMTAN, for 5'-methylthioadenosine nucleosidase), which encodes a polypeptide similar to EcMTAN from Escherichia coli. Deletion analyses showed that CBL3 utilizes the different structural modules to interact with its distinct target proteins, CIPKs and AtMTAN. In vitro and in vivo analyses verified that CBL3 and AtMTAN physically associate only in the presence of Ca(2+). In addition, we empirically demonstrated that the AtMTAN protein indeed possesses the MTAN activity, which can be inhibited specifically by Ca(2+)-bound CBL3. Overall, these findings suggest that the CBL family members can relay the calcium signals in more diverse ways than previously thought. We also discuss a possible mechanism by which the CBL3-mediated calcium signaling regulates the biosynthesis of ethylene and polyamines, which are involved in plant growth and development as well as various stress responses.