The majority of the clinically approved iron oxide nanoparticles (IO NPs) used as contrast agents for magnetic resonance imaging (MRI) have been withdrawn from the market either due to safety concerns or lack of profits. To address this challenge, liposomes have been used to prepare IO-based T2 contrast agents. We studied the influence of different phospholipids on the relaxivity (r2) values of magneto-liposomes (MLs) containing magnetic NPs in the bilayer, where a strong correlation between the bilayer fluidity and r2 is clearly shown. Embedding 5-nm IO NPs in the lipid bilayer leads to a significant improvement in their relaxivity, where r2 values range from 153 ± 5 s−1 mM−1 for DPPC/cholesterol/DSPE-PEG (96/50/4) up to 673 ± 12 s−1 mM−1 for DOPC/DSPE-PEG (96/4), compared to “free” IO NPs with an r2 value of 16 s−1 mM−1, measured at 9.4 T MRI scanner. In vitro MRI measurements, together with the ICP-MS analysis, revealed MLs as highly selective contrast agents that were preferentially taken up by cancerous T24 cells, which led to an improvement in the contrast and an easier distinction between the healthy and the cancerous cells. A careful selection of the lipid bilayer to prepare MLs could offer efficient MRI contrast agents, even at very low IO NP concentrations.