A thorough understanding of the molecular mechanisms of protein-nanoparticle associations facilitates the development of novel applications in nanoscience and nanotechnology. As an important functional protein that mediates protein degradation pathway, ubiquitin is abundant and regulates a large number of cellular processes. Thus, in this study, we investigated, with a combined experimental and theoretical approach, the interaction of ubiquitin with graphene quantum dots (GQDs), an important class of novel carbon nanomaterials which has attracted intense attention lately due to its great potential in biomedical applications. Our surface plasmon resonance (SPR) studies indicated a high binding affinity between ubiquitin and GQDs, and the circular dichroism (CD) spectroscopy revealed a marked reduction in ubiquitin's β-sheet content. The nuclear magnetic resonance (NMR) spectroscopy unambiguously identified the ubiquitin-GQDs interaction sites at the residue level, with majority of them residing near the β-sheet regions. Molecular dynamics (MD) simulations further revealed the microscopic picture of the ubiquitin-GQDs interaction at atomic detail, supporting the experimental findings. Overall, we provide a deep comprehension of protein-GQDs interaction through identification and characterization of the key binding sites, which may pave the way for a better guidance on safe design and development of potential applications using graphene nanomaterials.