Metal surfaces have long been known to reconstruct, significantly influencing their structural and catalytic properties. Many key mechanistic aspects of these subtle transformations remain poorly understood due to limitations of previous simulation approaches. Using active learning of Bayesian machine-learned force fields trained from ab initio calculations, we enable large-scale molecular dynamics simulations to describe the thermodynamics and time evolution of the low-index mesoscopic surface reconstructions of Au (e.g., the Au(111)-Herringbone,' Au(110)-(1x2)-Missing-Row,' and Au(100)-`Quasi-Hexagonal' reconstructions). This capability yields direct atomistic understanding of the dynamic emergence of these surface states from their initial facets, providing previously inaccessible information such as nucleation kinetics and a complete mechanistic interpretation of reconstruction under the effects of strain and local deviations from the original stoichiometry. We successfully reproduce previous experimental observations of reconstructions on pristine surfaces and provide quantitative predictions of the emergence of spinodal decomposition and localized reconstruction in response to strain at non-ideal stoichiometries. A unified mechanistic explanation is presented of the kinetic and thermodynamic factors driving surface reconstruction. Furthermore, we study surface reconstructions on Au nanoparticles, where characteristic (111) and (100) reconstructions spontaneously appear on a variety of high-symmetry particle morphologies. The training data, MLFF, and subsequent simulations are provided for reproducibility.