Recently obtained single-crystal structure of a thiolate-protected gold cluster shows that all thiolate groups form "staple" motifs on the cluster surface. To find out the driving force for such a formation, we use first-principles density functional theory simulations to model formation of "staple" motifs on an Au38 cluster from zero to full coverage. By geometry optimization, molecular dynamics, and simulated annealing, we show that formation of "staples" is strongly preferred on a cluster surface and helps stabilize the cluster by pinning the surface Au atoms and increasing the HOMO-LUMO gap. We devise a method to generate initial structural models for thiolate-protected gold clusters by adding "staples" to the cluster surface. Using this method, we obtain a staple-covered, low-energy structure for Au38(SCH3)24, a much studied cluster whose structure is not yet known. Optical band-edge energy computed from time-dependent DFT for our Au38(SCH3)24 structure shows good agreement with experiment.