We demonstrate that the discrepancy between the anomalous magnetic moment measured at BNL and Fermilab and the Standard Model prediction could be explained within the context of low-scale gravity and large extra-dimensions. The dominant contribution to $(g-2)_mu$ originates in Kaluza-Klein (KK) excitations (of the lepton gauge boson) which do not mix with quarks (to lowest order) and therefore can be quite light avoiding LHC constraints. We show that the KK contribution to $(g-2)_mu$ is universal with the string scale entering as an effective cutoff. The KK tower provides a unequivocal distinctive signal which will be within reach of the future muon smasher.