Clusters containing a single magnetic impurity were investigated by scanning tunneling microscopy, spectroscopy, and ab initio electronic structure calculations. The Kondo temperature of a Co atom embedded in Cu clusters on Cu(111) exhibits a nonmonotonic variation with the cluster size. Calculations model the experimental observations and demonstrate the importance of the local and anisotropic electronic structure for correlation effects in small clusters.