We calculate a new contribution to the axion mass that arises from gluons propagating in a 5th dimension at high energies. By uplifting the 4D instanton solution to five dimensions, the positive frequency modes of the Kaluza-Klein states generate a power-law term in the effective action that inversely grows with the instanton size. This causes 5D small instantons to enhance the axion mass in a way that does not spoil the axion solution to the strong CP problem. Moreover this enhancement can be much larger than the usual QCD contribution from large instantons, although it requires the 5D gauge theory to be near the non-perturbative limit. Thus our result suggests that the mass range of axions (or axion-like particles), which is important for ongoing experimental searches, can depend sensitively on the UV modification of QCD.