Colloidal nanoparticles (NPs) have attracted significant attention due to their unique physicochemical properties suitable for diagnosing and treating different human diseases. Nevertheless, the successful implementation of NPs in medicine demands a proper understanding of their interactions with the different proteins found in biological fluids. Once introduced into the body, NPs are covered by a protein corona (PC) that determines the biological behavior of the NPs. The formation of the PC can eventually favor the rapid clearance of the NPs from the body before fulfilling the desired objective or lead to increased cytotoxicity. The PC nature varies as a function of the different repulsive and attractive forces that govern the NP-protein interaction and their colloidal stability. This review focuses on the phenomenon of PC formation on NPs from a physicochemical perspective, aiming to provide a general overview of this critical process. Main issues related to NP toxicity and clearance from the body as a result of protein adsorption are covered, including the most promising strategies to control PC formation and, thereby, ensure the successful application of NPs in nanomedicine.