Fundamental understanding of the early stages of electrodeposition at the nanoscale is key to address the challenges in a wide range of applications. Despite having been studied for decades, a comprehensive understanding of the whole process is still out of reach. In this work, we introduce a novel modelling approach that couples a finite element method (FEM) with a random walk algorithm, to study the early stages of nanocluster formation, aggregation and growth, during electrochemical deposition. This approach takes into account not only electrochemical kinetics and transport of active species, but also the surface diffusion and aggregation of adatoms and small nanoclusters. The simulation results reveal that the relative surface mobility of the nanoclusters compared to that of the adatoms plays a crucial role in the early growth stages. The number of clusters, their size and their size dispersion are influenced more significantly by nanocluster mobility than by the applied overpotential itself. Increasing the overpotential results in shorter induction times and leads to aggregation prevalence at shorter times. A higher mobility results in longer induction times, a delayed transition from nucleation to aggregation prevalence, and as a consequence, a larger surface coverage of smaller clusters with a smaller size dispersion. As a consequence, it is shown that a classical first-order nucleation kinetics equation cannot describe the evolution of the number of clusters with time, N(t), in potentiostatic electrodeposition. Instead, a more accurate representation of N(t) is provided. We show that an evaluation of N(t), which neglects the effect of nanocluster mobility and aggregation, can induce errors of several orders of magnitude in the determination of nucleation rate constants. These findings are extremely important towards evaluating the elementary electrodeposition processes, considering not only adatoms, but also nanoclusters as building blocks.