Strategies of manipulating immunosuppressive regulatory T cells (Treg) in cancer patients are currently evaluated in clinical trials. Treg suppress immune responses of tumor-specific T cells; yet, relatively little is known about the impact of Treg on innate immune cells in tumor models in vivo. Many tumors lose expression of MHC class I. Therefore, our study aimed at defining strategies to strengthen immune responses against a high tumor burden of the MHC class I-deficient mouse lymphoma RMA-S. We demonstrate that Treg depletion in mice led to tumor rejection that was dependent on T cells, NK cells and IFN-gamma. In the absence of Treg elevated levels of IFN-gamma were produced by tumor-infiltrating T cells and NK cells. Tumor rejection observed in the absence of Treg correlated with a substantial IFN-gamma-dependent increase in the numbers of tumor-infiltrating leukocytes. The most abundant cell population in the tumors was macrophages. Tumor-infiltrating macrophages from Treg-depleted mice expressed increased amounts of MHC class II, produced highly enhanced levels of pro-inflammatory cytokines and inhibited tumor cell proliferation. It was reported that tumor-infiltrating macrophages have multi-faceted functions promoting or counteracting tumor growth. In our study, high numbers of macrophages infiltrating RMA-S tumors in the absence of Treg correlated with tumor rejection suggesting that macrophages are additional targets for Treg-mediated immune suppression in cancer.