Recently obtained single-crystal structure of a thiolate-protected go cluster sows 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 Au-38 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 Au-38 (SCH3)(24), a much studied cluster whose structure is not yet known. Optical band-edge energy computed from time-dependent DFT for our Au-38(SCH3)(24) structure shows good agreement with experiment.