Abstract Background It has been almost a decade since HIV was declared a national disaster in Kenya. Antiretroviral therapy (ART) provision has been a mainstay of HIV treatment efforts globally. In Kenya, the government started ART provision in 2003 with significantly scale-up after 2006. This study aims to demonstrate changes in population-level HIV mortality in two high HIV prevalence slums in Nairobi with respect to the initiation and subsequent scale-up of the national ART program. Methods We used data from 2070 deaths of people aged 15–54 years that occurred between 2003 and 2010 in a population of about 72,000 individuals living in two slums covered by the Nairobi Urban Health and Demographic Surveillance System. Only deaths for which verbal autopsy was conducted were included in the study. We divided the analysis into two time periods: the “early” period (2003–2006) which coincides with the initiation of ART program in Kenya, and the “late” period (2007–2010) which coincides with the scale up of the program nationally. We calculated the mortality rate per 1000 person years by gender and age for both periods. Poisson regression was used to predict the risk of HIV mortality in the two periods while controlling for age and gender. Results Overall, HIV mortality declined significantly from 2.5 per 1,000 person years in the early period to 1.7 per 1,000 person years in the late period. The risk of dying from HIV was 53 percent less in the late period compared to the period before, controlling for age and gender. Women experienced a decline in HIV mortality between the two periods that was more than double that of men. At the same time, the risk of non-HIV mortality did not change significantly between the two time periods. Conclusions Population-level HIV mortality in Nairobi’s slums was significantly lower in the approximate period coinciding with the scale-up of ART provision in Kenya. However, further studies that incorporate ART coverage data in mortality estimates are needed. Such information will enhance our understanding of the full impact of ART scale-up in reducing adult mortality among marginalized slum populations in Kenya.