For the purpose of successfully monitoring labeled cells, optimum labeling efficiency without any side effect is a prerequisite. Magnetic cellular imaging is a new and growing field that allows the visualization of implanted cells in vivo. Herein, superparamagnetic iron oxide (SPIO) nanoparticles were conjugated with a non-toxic protein transduction domain (PTD), identified by the authors and termed low molecular weight protamine (LMWP), to generate efficient and non-toxic cell labeling tools. The cells labeled with LMWP-SPIO presented the highest iron content compared to those labeled with naked SPIO and the complex of SPIO with poly-L-lysine, which is currently used as a transfection agent. In addition to the iron content assay, Prussian staining and confocal observation demonstrated the highest intracellular LMWP-SPIO presence, and the labeling procedure did not alter the cell differentiation capacity of mesenchymal stem cells. Taken together, cell permeable magnetic nanoparticles conjugated with LMWP can be suggested as labeling tools for efficient magnetic imaging of transplanted cells.