Evolution of SARS-CoV-2 in immunocompromised hosts may result in novel variants with changed properties, but the mode of selection underlying this process remains unclear. While escape from humoral immunity certainly plays a role in intra-host evolution, escape from cellular immunity is poorly understood. Here, we report a case of long-term COVID-19 in an immunocompromised patient with non-Hodgkin’s lymphoma who received treatment with rituximab and lacked neutralizing antibodies. Over the 318 days of the disease, the SARS-CoV-2 genome gained a total of 40 changes, 34 of which were present by the end of the study period. Among the acquired mutations, 12 reduced or prevented binding of known immunogenic SARS-CoV-2 HLA class I antigens, suggesting that virus immunoediting is largely driven by cytotoxic CD8 T cell clones. The two changes with the strongest effect, nsp3:T504A and nsp3:T504P, were experimentally assessed in a cytotoxic assay of the patient's CD8 T cells. Both these changes were associated with immune escape, with a stronger effect observed for nsp3:T504P, the change which ultimately got fixed. Together, these results suggest that CD8 T cell escape may be an underappreciated contributor to SARS-CoV-2 evolution in humans.