Protein-nanoparticle associations have important applications in nanoscience and nanotechnology such as targeted drug delivery and theranostics. However, the mechanisms by which proteins recognize nanoparticles and the determinants of specificity are still poorly understood at the microscopic level. Gold is a promising material in nanoparticles for nanobiotechnology applications because of the ease of its functionalization and its tunable optical properties. Ubiquitin is a small, cysteine-free protein (ubiquitous in eukaryotes) whose binding to gold nanoparticles has been characterized recently by nuclear magnetic resonance (NMR). To reveal the molecular basis of these protein-nanoparticle interactions, we performed simulations at multiple levels (ab initio quantum mechanics, classical molecular dynamics and Brownian dynamics) and compared the results with experimental data (circular dichroism and NMR). The results provide a model of the ensemble of structures constituting the ubiquitin-gold surface complex, and insights into the driving forces for the binding of ubiquitin to gold nanoparticles, the role of nanoparticle surfactants (citrate) in the association process, and the origin of the perturbations in the NMR chemical shifts.