Mesenchymal stem cells (MSC) comprise a heterogeneous population of rapidly proliferating cells that can be isolated from adult (e.g., bone marrow, adipose tissue) as well as fetal (e.g., umbilical cord) tissues (termed bone marrow (BM)-, adipose tissue (AT)-, and umbilical cord (UC)-MSC, respectively) and are capable of differentiation into a wide range of non-hematopoietic cell types. An additional, unique attribute of MSC is their ability to home to tumor sites and to interact with the local supportive microenvironment which rapidly conceptualized into MSC-based experimental cancer cytotherapy at the turn of the century. Towards this purpose, both naïve (unmodified) and genetically modified MSC (GM-MSC; used as delivery vehicles for the controlled expression and release of antitumorigenic molecules) have been employed using well-established in vitro and in vivo cancer models, albeit with variable success. The first approach is hampered by contradictory findings regarding the effects of naïve MSC of different origins on tumor growth and metastasis, largely attributed to inherent biological heterogeneity of MSC as well as experimental discrepancies. In the second case, although the anti-cancer effect of GM-MSC is markedly improved over that of naïve cells, it is yet apparent that some protocols are more efficient against some types of cancer than others. Regardless, in order to maximize therapeutic consistency and efficacy, a deeper understanding of the complex interaction between MSC and the tumor microenvironment is required, as well as examination of the role of key experimental parameters in shaping the final cytotherapy outcome. This systematic review represents, to the best of our knowledge, the first thorough evaluation of the impact of experimental anti-cancer therapies based on MSC of human origin (with special focus on human BM-/AT-/UC-MSC). Importantly, we dissect the commonalities and differences as well as address the shortcomings of work accumulated over the last two decades and discuss how this information can serve as a guide map for optimal experimental design implementation ultimately aiding the effective transition into clinical trials.