Here we follow, both experimentally and theoretically, the development of magnetism in Tb clusters from the atomic limit, adding one atom at a time. The exchange interaction is, surprisingly, observed to drastically increase compared to that of bulk, and to exhibit irregular oscillations as a function of the interatomic distance. From electronic structure theory we find that the theoretical magnetic moments oscillate with cluster size in exact agreement with experimental data. Unlike the bulk, the oscillation is not caused by the RKKY mechanism. Instead, the inter-atomic exchange is shown to be driven by a competition between wave-function overlap of the 5d shell and the on-site exchange interaction, which leads to a competition between ferromagnetic double-exchange and antiferromagnetic super-exchange. This understanding opens up new ways to tune the magnetic properties of rare-earth based magnets with nano-sized building blocks.