We conducted a study to assess trends in haemoglobin recovery among HIV-infected patients initiated on zidovudine-based combination antiretroviral therapy (cART) stratified by baseline haemoglobin level. Haemoglobin data from non-pregnant adult patients initiating cART in rural north-central Nigeria between June 2009 and May 2011 were analysed using a linear mixed effects model to assess the interaction between time, zidovudine-containing regimen and baseline haemoglobin level on the outcome of subsequent haemoglobin level. Best-fit curves were created for baseline haemoglobin in the 10th, 25th, 75th and 90th percentiles. We included 313 patients with 736 measures of haemoglobin in the analysis (239 on zidovudine and 74 on non-zidovudine-containing regimens). Median haemoglobin increased over time in both groups, with differences in haemoglobin response over time related to baseline haemoglobin levels and zidovudine use (p = 0.003). The groups of patients on zidovudine at the 10th and 90th percentiles had downward sloping curves while all other groups had upward trending haemoglobin levels. Although haemoglobin levels increased overall for patients on zidovudine-containing regimens, for those in the 10th and 90th percentiles haemoglobin levels trended downward over time. These results have implications for decisions regarding when to initiate, switch from or avoid the use of zidovudine.