Non-Hodgkin's lymphoma (NHL) remains the second most common malignant complication in patients with human immunodeficiency virus (HIV) infection. Even though NHL is commonly chemosensitive to primary treatment, failure or relapse still occurs in a large number of patients. We conducted this retrospective study to evaluate the efficacy and safety of gemcitabine, dexamethasone, and cisplatin (GDP) for relapsed or refractory AIDS-related NHL (AIDS-NHL). Forty-eight patients with relapsed or refractory AIDS-NHL were treated with intravenous combination chemotherapy with GDP. The overall objective response rate was 54.1 % (95 % confidence interval, CI, 40.1–68.3 %), with 10 complete responses and 16 partial responses. The 2-year overall survival rate (OS) was 70.8 % (95 % CI 58.0–83.7 %), and the 5-year OS was 41.7 % (95 % CI 27.7–55.6 %). The 2-year progression-free survival rate (PFS) was 37.5 % (95 % CI 23.8–51.2 %), and the 5-year PFS was 25.0 % (95 % CI 12.8–37.3 %). The median progression-free survival was 8.8 months (95 % CI 0–20.3 months), and the median overall survival was 40.6 months (95 % CI 22.6–58.6 months). Patients with B cell tumors who relapsed but had no B symptoms were clinical stage I/II, had infiltration fewer than two extranodal sites, had CD4+ counts >200 cells/μL, and had lactate dehydrogenase (LDH) less than the upper limit of normal benefited from GDP. The level of LDH had a significant impact on the response rate to chemotherapy with GDP (P = 0.015). Myelosuppression was the main side effect; the incidence of grade 3–4 anemia was 8.3 %; leukopenia, 37.5 %; and thrombocytopenia, 48.3 %. Univariate and multivariate analyses were performed to determine variables for OS and PFS. This study confirms that GDP is an effective and safe salvage regimen in relapsed or refractory AIDS-NHL, was associated with modest declines in CD4+ lymphocyte counts, and did not promote HIV-1 viral replication.