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 α-galactosylceramide (α-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 α-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 α-GalCer, and the survival rate jumped to 85%. Our results imply a potential application of combining T_reg cell depletion with α-GalCer to stimulate NK T cells for cancer therapy.