Lithium metal plating is a critical safety issue in Li-ion cells with graphite anodes, and contributes significantly to ageing, drastically limiting the lifetime and inducing capacity loss. Nonetheless, the nucleation mechanism of metallic Li on graphite anodes is still poorly understood. But in-depth understanding is needed to rationally design mitigation measures. In this work, we conducted First-Principles studies to elucidate the Li nucleation mechanism on graphite surfaces. These large-scale density-functional-theory (DFT) calculations indicate that nano-particulate Li forms much more readily than classical nucleation theory predicts. Further, our calculations indicate a crucial role of topological surface states near the zigzag edge, lowering the nucleation barrier by a further 1.32 eV relative to nucleation on the basal plane. Li nucleation, therefore, is likely to initiate at or near the zigzag edges of graphitic particles. Finally, we suggest that chemical doping with a view to reducing the effect of the topological surface states might be a potential mitigation strategy to increase nucleation barriers and reduce the propensity to plate Li near the zigzag edge.