We report a quantitative atomic scale study of nucleation kinetics on an inhomogeneous substrate. Our model system, Al/Au(111)-(root 3 x 22), reveals a distinct nucleation transition due to the repulsive nature of surface dislocations. Whereas for T < 200 K Al adatoms are confined to quasipseudomorphic stacking areas experiencing a very small diffusion barrier (30 +/- 5 meV), at T > 200 K surface dislocations, representing repulsive barriers of Delta E approximate to 560 meV, can be surmounted. The results illustrate the significance of surface dislocations as repulsive line defects in nucleation and growth.