Multiple Myeloma (MM) is preceded by the clinically stable condition monoclonal gammopathy of undetermined significance (MGUS). Critical immune events that discriminate MGUS from newly diagnosed MM (ND)MM patients remain unknown, but may involve changes in the regulatory T cell (Treg) compartment that favor myeloma growth. To address this possibility, we used mass cytometry and the unsupervised clustering algorithm Flow self-organizing map (FlowSOM) to interrogate the distribution of multiple subsets within CD25+CD127low/negTreg in matched bone marrow (BM) and peripheral blood (PB) of MGUS and NDMM patients. Both mass cytometry and flow cytometry confirmed a trend toward prevalence of CD39−Treg within the Treg compartment in BM and PB of NDMM patients compared to CD39−Treg in MGUS patients. FlowSOM clustering displayed a phenotypic organization of Treg into 25 metaclusters that confirmed Treg heterogeneity. It identified two subsets which emerged within CD39−Treg of NDMM patients that were negligible or absent in CD39−Treg of MGUS patients. One subset was found in both BM and PB which phenotypically resembled activated Treg based on CD45RO, CD49d, and CD62L expression; another subset resembled BM-resident Treg based on its tissue-resident CD69+CD62L−CD49d− phenotype and restricted location within the BM. Both subsets co-expressed PD-1 and TIGIT, but PD-1 was expressed at higher levels on BM-resident Treg than on activated Treg. Within BM, both subsets had limited Perforin and Granzyme B production, whilst activated Treg in PB acquired high Perforin and Granzyme B production. In conclusion, the use of mass cytometry and FlowSOM clustering discovered two discrete subsets of CD39−Treg which are discordant in MGUS and NDMM patients and may be permissive of myeloma growth which warrants further study. Understanding the regulatory properties of these subsets may also advance MGUS and MM diagnosis, prognosis, and therapeutic implications for MM patients.