Ligation of inhibitory receptors renders natural killer (NK) cells inactive against autologous tumors. Recently, the proteasome inhibitor bortezomib was shown to sensitize tumors to autologous NK-cell cytotoxicity in vitro. Here, we show bortezomib augments the antitumor effects of syngeneic NK-cell infusions in tumor-bearing animals; this effect is further enhanced in regulatory T cell (Treg cell)–depleted hosts. In vitro, bortezomib-treated tumors had higher tumor necrosis factor–related apoptosis-inducing ligand (TRAIL) and perforin/granzyme-mediated caspase-8 activity, which enhanced their susceptibility to NK-cell lysis. Bioluminescence imaging of mice with established tumors showed treatment with bortezomib and syngeneic NK cells reduced tumor growth and prolonged survival compared with controls receiving bortezomib or NK cells alone. In contrast, tumor progression was not delayed when animals received bortezomib and perforin-deficient NK cells, showing drug-induced augmentation in NK-cell cytotoxicity was mediated through perforin/granzyme. Furthermore, tumor growth was slower in bortezomib-treated recipients when host Treg cells were eradicated with anti-CD25 antibody before infusing NK cells compared with mice without Treg-cell ablation (tumor doubling time, 16.7 vs 4.9 days, respectively; P = .02). These findings suggest that depletion of Treg cells followed by bortezomib-induced tumor sensitization to autologous NK cells could be used as a novel strategy to treat cancer.