Recent structural determinations have shown that thiolate-protected gold nanoparticles are not as regular and symmetric as initially thought, but characteristic substructures (staple motifs) are formed on their surface. However, their mechanism of formation, especially the fate of the sulfur protons upon thiol binding, remains one of the most intriguing unanswered questions in gold cluster chemistry. By means of ab initio molecular dynamics (AIMD), we monitor the trajectory of thiol protons reacting with a gold cluster, demonstrating that the staple motif forms in a multiple-pathway chemical reaction, releasing molecular hydrogen. The results obtained also reconcile the conclusions of structural determinations with the interpretations of spectroscopic experiments on solution, suggesting the presence of intact thiols or chemisorbed hydrogen.