The increasing applications of nanotechnology in medicine rely on the fact that engineered nanomaterials, such as diagnostic and therapeutic nanoparticles, are able to translocate across the cellular membrane and reach their site of action without toxic effects. One of the first steps into assessing the NP cytotoxicity requires a thorough understanding of the nanoparticle-membrane interaction mechanism. We have computationally investigated, using unprecedented spatiotemporal effort, the structure and dynamics of anionic NP partitioning in explicit cholesterol-containing membranes. Our results show that NP partitioning in the membrane is accompanied by the rearrangement of the NP surface ligands and causes the re-organization of the lipids and cholesterol in its vicinity. In this context, our study is an early step towards novel strategies for tailored decoration of NPs aiming to selectively target specific cells based on their cholesterol content.