The tumor immune microenvironment plays a critical role in cancer progression and response to immunotherapy in clear cell renal cell carcinoma (ccRCC), yet the composition and phenotypic states of immune cells in this tumor are incompletely characterized. We performed single-cell RNA and T cell receptor sequencing on 164,722 individual cells from tumor and adjacent non-tumor tissue in patients with ccRCC across disease stages: early, locally advanced, and advanced/metastatic. Terminally exhausted CD8+ T cells were enriched in metastatic disease and were restricted in T cell receptor diversity. Within the myeloid compartment, pro-inflammatory macrophages were decreased, and suppressive M2-like macrophages were increased in advanced disease. Terminally exhausted CD8+ T cells and M2-like macrophages co-occurred in advanced disease and expressed ligands and receptors that support T cell dysfunction and M2-like polarization. This immune dysfunction circuit is associated with a worse prognosis in external cohorts and identifies potentially targetable immune inhibitory pathways in ccRCC.