Mesenchymal stromal cells (MSCs) are promising candidates in regenerative cell-therapies. However, optimizing their number and route of delivery remains a critical issue, which can be addressed by monitoring the MSCs' bio-distribution in vivo using super-paramagnetic iron-oxide nanoparticles (SPIONs). In this study, amino-polyvinyl alcohol coated (A-PVA) SPIONs are introduced for cell-labeling and visualization by magnetic resonance imaging (MRI) of human MSCs. Size and surface charge of A-PVA-SPIONs differ depending on their solvent. Under MSC-labeling conditions, A-PVA-SPIONs have a hydrodynamic diameter of 42 ± 2 nm and a negative Zeta potential of 25 ± 5 mV, which enable efficient internalization by MSCs without the need to use transfection agents. Transmission X-ray microscopy localizes A-PVA-SPIONs in intracellular vesicles and as cytosolic single particles. After identifying non-interfering cell-assays and determining the delivered and cellular dose, in addition to the administered dose, A-PVA-SPIONs are found to be non-toxic to MSCs and non-destructive towards their multi-lineage differentiation potential. Surprisingly, MSC migration is increased. In MRI, A-PVA-SPION-labeled MSCs are successfully visualized in vitro and in vivo. In conclusion, A-PVA-SPIONs have no unfavorable influences on MSCs, although it becomes evident how sensitive their functional behavior is towards SPION-labeling. And A-PVA-SPIONs allow MSC-monitoring in vivo.