Since multiple lines of experimental and clinical data clearly identified regulatory T cells as an integral part of the immune response, these cells have become a major focus of investigation in tumor immunology. Regulatory T cells are in place to dampen ongoing immune responses and to prevent autoimmunity, but they also have profound effects in blocking therapeutic anti-tumor activity. Therefore regulatory T cells are seen as a major hurdle that must be overcome in order for cancer immunotherapy to reach its therapeutic potential. Regulatory T cells are heterogeneous with sub-populations that exhibit distinct functional features. Here we will review the individual sub-populations in regards to their mode of action and their potential impact on blocking anti-tumor immunity. Approaches to measure function and frequency of regulatory T cells in model systems and clinical trails will be discussed. Finally, we will describe possible ways to interfere with regulatory T cell-mediated immune suppression with the focus on recent pre-clinical and clinical findings.