Relatlimab (rela; anti-LAG-3) plus nivolumab (nivo; anti-PD-1) is safe and effective for treatment of advanced melanoma. We designed a trial (NCT03743766) where advanced melanoma patients received rela, nivo, or rela+nivo to interrogate the immunologic mechanisms of rela+nivo. Analysis of biospecimens from this ongoing trial demonstrated that rela+nivo led to enhanced capacity for CD8 T cell receptor signaling and altered CD8 T cell differentiation, leading to heightened cytotoxicity despite the retention of an exhaustion profile. Co-expression of cytotoxic and exhaustion signatures was driven by PRDM1, BATF, ETV7, and TOX. Effector function was upregulated in clonally expanded CD8 T cells that emerged after rela+nivo. A rela+nivo intratumoral CD8 T cell signature was associated with a favorable prognosis. This intratumoral rela+nivo signature was validated in peripheral blood as an elevated frequency of CD38TIM3CD8 T cells. Overall, we demonstrated that cytotoxicity can be enhanced despite the retention of exhaustion signatures, which will inform future therapeutic strategies.