The unprecedented success of immune checkpoint inhibitors has given rise to a rapidly growing number of immuno-oncology agents undergoing preclinical and clinical development and an exponential increase in possible combinations. Defining a clear rationale for combinations by identifying synergies between immunomodulatory pathways has therefore become a high priority. Immunosuppressive regulatory T cells (Tregs) within the tumor microenvironment (TME) represent a major roadblock to endogenous and therapeutic tumor immunity. However, Tregs are also essential for the maintenance of immunological self-tolerance, and share many molecular pathways with conventional T cells including cytotoxic T cells, the primary mediators of tumor immunity. Hence the inability to specifically target and neutralize Tregs within the TME of cancer patients without globally compromising self-tolerance poses a significant challenge. Here we review recent advances in the characterization of tumor-infiltrating Tregs with a focus on costimulatory and inhibitory receptors. We discuss receptor expression patterns, their functional role in Treg biology and mechanistic insights gained from targeting these receptors in preclinical models to evaluate their potential as clinical targets. We further outline a framework of parameters that could be used to refine the assessment of Tregs in cancer patients and increase their value as predictive biomarkers. Finally, we propose modalities to integrate our increasing knowledge on Treg phenotype and function for the rational design of checkpoint inhibitor-based combination therapies. Such combinations have great potential for synergy, as they could concomitantly enhance cytotoxic T cells and inhibit Tregs within the TME, thereby increasing the efficacy of current cancer immunotherapies.