An important development in tumor immunology was the identification of highly diverse tumor-infiltrating leukocyte subsets that can play strikingly antagonistic functions. Namely, "anti-tumor" vs. "pro-tumor" roles have been suggested for Th1 and Th17 subsets of CD4(+) T cells, Type I or Type II NKT cells, M1 and M2 macrophages, or N1 and N2 neutrophils, respectively. While these findings are being validated in cancer patients, it is also clear that the balance between infiltrating CD8(+) cytotoxic and Foxp3(+) regulatory T cells has prognostic value. Here we review the pre-clinical and clinical data that have shaped our current understanding of tumor-infiltrating leukocytes.