Using scanning tunneling microscopy, we demonstrate that the nucleation density of Fe islands on the surface of nanoscale Pb films oscillates with the film thickness, providing a direct manifestation of the quantum size effect on surface diffusion. The Fe adatom diffusion barriers were derived to be 204+/-5 and 187+/-5 meV on a 21 and 26 monolayer (ML) Pb film, respectively, by matching the kinetic Monte Carlo simulations to the experimental island densities. The effect is further illustrated by the growth of Fe islands on wedged Pb films, where the Fe island density is consistently higher on the odd-layer films than on the even-layer films in the thickness range of 11 to 15 ML.