Both invariant natural killer T (NK T) cells and CD4(+)CD25(+) T regulatory cells (T(regs)) regulate the immune system to maintain homeostasis. In a tumour setting, NK T cells activated by alpha-galactosylceramide (alpha-GalCer) execute anti-tumour activity by secreting cytokines. By contrast, T(regs) intrinsically suppress antigen-specific immune responses and are often found to be elevated in tumour patients. In this study, we have shown that T(regs) regulate NK T cell function negatively in vitro, suggesting a direct interaction between these cell types. In a murine mammary tumour model, we demonstrated that administration of either alpha-GalCer or anti-CD25 antibody alone markedly suppressed tumour formation and pulmonary metastasis, and resulted in an increase in the survival rate up to 44% (from a baseline of 0%). When treatments were combined, depletion of T(regs) boosted the anti-tumour effect of alpha-GalCer, and the survival rate jumped to 85%. Our results imply a potential application of combining T(reg) cell depletion with alpha-GalCer to stimulate NK T cells for cancer therapy.