Anemia is a common problem after renal transplantation. Therefore, the patients are treated with erythropoietin stimulating agents (ESAs). The varying response to treatment contributes to hemoglobin variability, which might be associated with mortality. We conducted a retrospective cohort study of first kidney allograft recipients between 1990 and 2008 represented in the Austrian Transplant Registry. We included 1441 patients of whom 683 received ESAs at any time after transplantation. Cox regression with cubic splines and linear estimates and the purposeful selection algorithm of covariables were used. The measure of variability was the moving standard deviation computed at three monthly intervals for the entire graft life. The hazard ratio (HR) of mortality and graft loss in the spline models increased with hemoglobin variability. The linear HR for mortality was 2.35 (95% confidence interval 1.75–3.17, P < 0.001) and functional graft loss 2.45 (1.76–3.40, P < 0.001). In an adjusted Cox model (ESA use, hemoglobin, age, diabetes, days on dialysis, eGFR, biopsy confirmed acute rejection and year of transplantation), hemoglobin variability was associated with mortality (HR: 2.11; 1.51–2.94; P < 0.001). No association with functional graft loss could be detected (HR: 1.34; 0.93–1.93; P = 0.121). These findings suggest that hemoglobin variability is associated with mortality of renal allograft recipients.