By using fluorescence correlation spectroscopy (FCS), we have studied the adsorption of human serum albumin (HSA) onto Fe-Pt nanoparticles (NPs, 6 nm radius), CdSe/ZnS quantum dots (QDs, 5 nm radius) and Au and Ag nanoclusters (1-4 nm radius), which are enshrouded by various water-solubilizing surface layers exposing different chemical functional groups (carboxyl, amino and both), thereby endowing the NPs with different surface charges. We have also measured the effects of modified surface functionalizations on the protein via succinylation and amination. A step-wise increase in hydrodynamic radius with protein concentration was always observed, revealing formation of protein monolayers coating the NPs, independent of their surface charge. The differences in the thickness of the protein corona were rationalized in terms of the different orientations in which HSA adsorbs onto the NPs. The midpoints of the binding transition, which quantifies the affinity of HSA toward the NP, were observed to differ by almost four orders of magnitude. These variations can be understood in terms of specific Coulombic interactions between the proteins and the NP surfaces.