Natural killer T (iNKT) cells can help mediate immune surveillance against tumors in mice. Prior studies targeting human iNKT cells were limited to therapy of advanced cancer and led to only modest activation of innate immunity. Clinical myeloma is preceded by an asymptomatic precursor phase. Lenalidomide was shown to mediate antigen-specific costimulation of human iNKT cells. We treated 6 patients with asymptomatic myeloma with 3 cycles of combination of α-galactosylceramide–loaded monocyte-derived dendritic cells and low-dose lenalidomide. Therapy was well tolerated and led to reduction in tumor-associated monoclonal immunoglobulin in 3 of 4 patients with measurable disease. Combination therapy led to activation-induced decline in measurable iNKT cells and activation of NK cells with an increase in NKG2D and CD56 expression. Treatment also led to activation of monocytes with an increase in CD16 expression. Each cycle of therapy was associated with induction of eosinophilia as well as an increase in serum soluble IL2 receptor. Clinical responses correlated with pre-existing or treatment-induced antitumor T-cell immunity. These data demonstrate synergistic activation of several innate immune cells by this combination and the capacity to mediate tumor regression. Combination therapies targeting iNKT cells may be of benefit toward prevention of cancer in humans (trial registered at clinicaltrials.gov: NCT00698776).