Gemcitabine-based salvage therapy is considered an effective treatment for relapsed and refractory Non-Hodgkin’s lymphoma (NHL). We analyzed the outcome of 41 consecutive NHL patients treated with gemcitabine-based regimens between January 2007 and October 2015. Twenty-eight males and 13 females (median age 66.4 years) were included. The median follow-up from gemcitabine initiation was 7.3 months. Thirty patients (73%) had B-cell, and eleven (27%) had T-cell, lymphoma. All patients received a median of 2 prior regimens, of which at least 1 was anthracycline based. Twenty-eight patients (78%) received full-dose while 9 (22%) received reduced-dose regimens. The overall response rate was 37%, with 24% (n = 10) complete response, 12% (n = 5) partial response, and 63% (n = 22) progressive disease or stable disease. The median progression-free survival (PFS) was 47 days (range 12–1,318), the median overall survival (OS) was 1.9 years. Twenty patients (49%) died during follow-up. Grade 3–4 hematological toxicity was reported in 21 patients (51%). Relapsed vs. refractory disease, as well as a response to gemcitabine, predicted better PFS and OS. Use of a full-dose regimen predicted a better OS. Compared to previously published data, we observed less favorable outcomes. The administration of gemcitabine-based therapy as a salvage regimen for patients with relapsed or refractory NHL had limited success. Innovative therapies for these patients are an unmet need.