The electrodeposition of aluminum on the atomically smooth nitrogen-incorporated tetrahedral amorphous carbon (taC:N) electrode in ambient temperature AlCl3/EMIC chloroaluminate melts has been interpreted using a prior model of three-dimensional diffusion controlled nucleation and growth. Aluminum requires an unusually high overpotential for nucleation on taC:N because of the low density of intrinsic active sites, which act as critical nuclei during the initial stage of deposition. The current-time characteristics of nucleation on taC:N show a strong dependency on overpotential. Generation of additional, overpotential-induced active sites imposes a partial progressive nature on the overall nucleation process, resulting in a slight deviation from the limiting behavior of an ideal instantaneous nucleation model.