Nanoparticles (NPs) in the biological environment are exposed to a large variety and concentration of proteins. Proteins are known to adsorb in a 'corona' like structure on the surface of NPs. In this study, we focus on the effects of surface compositional and structural heterogeneity on protein adsorption by examining the interaction of self-assembled monolayer coated gold NPs (AuNPs) with two types of proteins: ubiquitin and fibrinogen. This work was designed to systematically investigate the role of surface heterogeneity in nanoparticle-protein interaction. We have chosen the particles as well as the proteins to provide different types (in distribution and length-scale) of heterogeneity. The goal was to unveil the role of heterogeneity and of its length-scale in the particle-protein interaction. Dynamic light scattering and circular dichroism spectroscopy were used to reveal different interactions at pH above and below the isoelectric points of the proteins, which is related to the charge heterogeneity on the protein surface. At pH 7.4, there was only a monolayer of proteins adsorbed onto the NPs and the secondary structure of proteins remained intact. At pH 4.0, large aggregates of nanoparticle-protein complexes were formed and the secondary structures of the proteins were significantly disrupted. In terms of interaction thermodynamics, results from isothermal titration calorimetry showed that ubiquitin adsorbed differently onto (1) AuNPs with charged and nonpolar terminals organized into nano-scale structure (66-34 OT), (2) AuNPs with randomly distributed terminals (66-34 brOT), and (3) AuNPs with homogeneously charged terminals (MUS). This difference in adsorption behavior was not observed when AuNPs interacted with fibrinogen. The results suggested that the interaction between the proteins and AuNPs was influenced by the surface heterogeneity on the AuNPs, and this influence depends on the scale of surface heterogeneity and the size of the proteins.