The immunomodulatory potential of mesenchymal stromal cells (MSCs) and regulatory T cells (T-reg) is well recognized by translational scientists in the field of regenerative medicine and cellular therapies. A wide range of preclinical studies as well as a limited number of human clinical trials of MSC therapies have not only shown promising safety and efficacy profiles but have also revealed changes in T-reg frequency and function. However, the mechanisms underlying this potentially important observation are not well understood and, consequently, the optimal strategies for harnessing MSC/T-reg cross-talk remain elusive. Cell-to-cell contact, production of soluble factors, reprogramming of antigen presenting cells to tolerogenic phenotypes, and induction of extracellular vesicles ("exosomes") have emerged as possible mechanisms by which MSCs produce an immune-modulatory milieu for T-reg expansion. Additionally, these two cell types have the potential to complement each other's immunoregulatory functions, and a combinatorial approach may exert synergistic effects for the treatment of immunological diseases. In this review, we critically assess recent translational research related to the outcomes and mechanistic basis of MSC effects on T-reg and provide a perspective on the potential for this knowledge base to be further exploited for the treatment of autoimmune disorders and transplants.