Vascularized composite allotransplantations (VCAs) are not routinely performed for tissue reconstruction because of the potentially harmful adverse effects associated with lifelong administration of immunosuppressive agents. Researchers have been eagerly seeking alternative methods that circumvent the long-term use of immunosuppressants. Mesenchymal stem cells (MSCs) show promise as an immunomodulatory therapeutic agent and are currently being tested in preclinical and clinical settings as therapies for autoimmune disorders or transplant rejection. The mechanisms by which MSCs modulate the immune response are still under thorough investigation, but these most likely involve expression of local factors influencing T-cell regulation, modulation of cytokine expression (e.g., IL-10, TGF-β, TNF-α, INF-γ, etc.), and interactions with dendritic or antigen presenting cells. In this paper, we summarize the current understanding of immunomodulation achieved by MSC therapies and introduce a possible outline for future clinical applications in VCA.