Background Studies of antiretroviral therapy (ART) programs in Africa have shown high initial mortality. Factors contributing to this high mortality are poorly described. The aim of the present study was to assess mortality and to identify predictors of mortality in HIV-infected patients starting ART in a rural hospital in Tanzania. Methods This was a cohort study of 320 treatment-naïve adults who started ART between October 2003 and November 2006. Reliable CD4 cell counts were not available, thus ART initiation was based on clinical criteria in accordance with WHO and Tanzanian guidelines. Kaplan-Meier models were used to estimate mortality and Cox proportional hazards models to identify predictors of mortality. Results Patients were followed for a median of 10.9 months (IQR 2.9–19.5). Overall, 95 patients died, among whom 59 died within 3 months of starting ART. Estimated mortality was 19.2, 29.0 and 40.7% at 3, 12 and 36 months, respectively. Independent predictors of mortality were severe anemia (hemoglobin <8 g/dL; adjusted hazard ratio [AHR] 9.20; 95% CI 2.05–41.3), moderate anemia (hemoglobin 8–9.9 g/dL; AHR 7.50; 95% CI 1.77–31.9), thrombocytopenia (platelet count <150 × 109/L; AHR 2.30; 95% CI 1.33–3.99) and severe malnutrition (body mass index <16 kg/m2; AHR 2.12; 95% CI 1.06–4.24). Estimated one year mortality was 55.2% in patients with severe anemia, compared to 3.7% in patients without anemia (P < 0.001). Conclusion Mortality was found to be high, with the majority of deaths occurring within 3 months of starting ART. Anemia, thrombocytopenia and severe malnutrition were strong independent predictors of mortality. A prognostic model based on hemoglobin level appears to be a useful tool for initial risk assessment in resource-limited settings.