For non-invasive stem cells tracking through MRI, it is important to understand the efficiency of in vitro labeling of stem cells with iron oxide with regard to its relaxation behavior. In this study, we have carried out a pilot study of labeling mice mesenchymal stem cells (mMSCs) with ultrasmall superparamagnetic iron oxide (USPIO) entrapped with poly-L-lysine (PLL) in different ratios and incubated with different times. Our results demonstrated that 50:1.5 μg/ml of iron oxide and PLL at an incubation time of 6 h with 10% serum concentration are sufficient enough for effective labeling. Optimized labeling showed that >98% of viability and <3% toxicity were observed at a total iron content of 11.8 pg/cell. In vitro relaxometry study showed that almost a 6.6 fold reduction in transverse relaxation time (T2) was observed after labeling as compared to unlabeled. IO-PLL complex was more effective than iron oxide alone in labeling and a detectable lower limit found to be hundred with optimized concentration. Significant increase in Oct-4 expression on day-3 after labeling was observed, whereas CD146 expression remains unchanged in real time RT-PCR. This optimized labeling method of MSCs may be very useful for cellular MRI and stem cells tracking studies.