There is still a lively debate about whether mesenchymal stem cells (MSCs) promote or suppress antitumor immune response. Although several possible explanations have been proposed, including different numbers of injected and engrafted MSCs, heterogeneity in phenotype, and function of tumor cells, the exact molecular mechanisms responsible for opposite effects of MSCs in modulation of antitumor immunity are still unknown. Herewith, we used a B16F10 murine melanoma model to investigate whether timing of MSC administration in tumor-bearing mice was crucially important for their effects on antitumor immunity. MSCs, intravenously injected 24 h after melanoma induction (B16F10+MSC1d-treated mice), significantly enhanced natural killer (NK) and T cell-driven antitumor immunity, suppressed tumor growth, and improved survival of melanoma-bearing animals. Significantly higher plasma levels of antitumorigenic cytokines (TNF-α and IFN-γ), remarkably lower plasma levels of immunosuppressive cytokines (TGF-β and IL-10), and a significantly higher number of tumor-infiltrating, IFN-γ-producing, FasL- and granzyme B-expressing NK cells, IL-17-producing CD4+Th17 cells, IFN-γ– and TNF-α-producing CD4+Th1 cells, and CD8+cytotoxic T lymphocytes (CTLs) were observed in B16F10+MSC1d-treated mice. On the contrary, MSCs, injected 14 days after melanoma induction (B16F10+MSC14d-treated mice), promoted tumor growth by suppressing antigen-presenting properties of tumor-infiltrating dendritic cells (DCs) and macrophages and by reducing tumoricidal capacity of NK cells and T lymphocytes. Significantly higher plasma levels of TGF-β and IL-10, remarkably lower plasma levels of TNF-α and IFN-γ, and significantly reduced number of tumor-infiltrating, I-A-expressing, and IL-12-producing macrophages, CD80- and I-A-expressing DCs, granzyme B-expressing CTLs and NK cells, IFN-γ– and IL-17-producing CTLs, CD4+Th1, and Th17 cells were observed in B16F10+MSC14d-treated animals. In summing up, the timing of MSC administration into the tumor microenvironment was crucially important for MSC-dependent modulation of antimelanoma immunity. MSCs transplanted during the initial phase of melanoma growth exerted tumor-suppressive effect, while MSCs injected during the progressive stage of melanoma development suppressed antitumor immunity and enhanced tumor expansion.