Few studies have demonstrated that innate lymphocytes play a major role in preventing spontaneous tumor formation. We evaluated the development of spontaneous tumors in mice lacking β-2 microglobulin (β2m; and thus MHC class I, CD1d, and CD16) and/or perforin, since these tumor cells would be expected to activate innate effector cells. Approximately half the cohort of perforin gene-targeted mice succumbed to spontaneous disseminated B cell lymphomas and in mice that also lacked β2m, the lymphomas developed earlier (by more than 100 d) and with greater incidence (84%). B cell lymphomas from perforin/β2m gene-targeted mice effectively primed cell-mediated cytotoxicity and perforin, but not IFN-γ, IL-12, or IL-18, was absolutely essential for tumor rejection. Activated NK1.1⁺ and γδTCR⁺ T cells were abundant at the tumor site, and transplanted tumors were strongly rejected by either, or both, of these cell types. Blockade of a number of different known costimulatory pathways failed to prevent tumor rejection. These results reflect a critical role for NK cells and γδTCR⁺ T cells in innate immune surveillance of B cell lymphomas, mediated by as yet undetermined pathway(s) of tumor recognition.