We find that citrate-stabilized gold nanoparticles aggregate and precipitate in saline solutions below the NaCl concentration of many bodily fluids and blood plasma. Our experiments indicate that this is due to complexation of the citrate anions with Na+ cations in solution. A dramatically enhanced colloidal stability is achieved when bovine serum albumin is adsorbed to the gold nanoparticle surface, completely preventing nanoparticle aggregation under harsh environmental conditions where the NaCl concentration is well beyond the isotonic point. Furthermore, we explore the mechanism of the formation of this albumin "corona" and find that monolayer protein adsorption is most likely ruled by hydrophobic interactions. As for many nanotechnology-based biomedical and environmental applications, particle aggregation and sedimentation are undesirable and could substantially increase the risk of toxicological side-effects, the formation of the BSA corona presented here provides a low-cost bio-compatible strategy for nanoparticle stabilization and transport in highly ionic environments.