Despite extensive studies on CD4+CD25+ regulatory T cells (Tregs), their application in adoptive transfer therapies is still not optimal in immune-competent wild-type (WT) animal models. Therefore, it is compelling to search for more potent Tregs for potential clinical application. Mounting evidence has shown that naturally occurring CD8+CD122+ T cells are also Tregs. However, their suppression in allograft rejection, efficiency in suppression and underlying mechanisms remain unclear. Using a murine allotransplantation model, we reported here that CD8+CD122+ Tregs were actually more potent in suppression of allograft rejection and underwent more rapid homeostatic proliferation than their CD4+CD25+ counterparts. Moreover, they produced more IL-10 and were more potent in suppressing T cell proliferation in vitro. Deficiency in IL-10 in CD4+CD25+ and CD8+CD122+ Tregs resulted in their reduced but equal suppression in vivo and in vitro, suggesting that IL-10 is responsible for more effective suppression by CD8+CD122+ than CD4+CD25+ Tregs. Importantly, transfer of CD8+CD122+ Tregs together with the administration of recombinant IL-15 significantly prolonged allograft survival in WT mice. Thus, for the first time, we demonstrate that naturally arising CD8+CD122+ Tregs not only inhibit allograft rejection but also exert this suppression more potently than their CD4+CD25+ counterparts. This novel finding may have important implications for tolerance induction.