Background: Non-HIV/AIDS-related diseases are gaining prominence as important causes of morbidity and mortality among people living with HIV. The purpose of this study was to characterize and compare changes over time in mortality rates and causes of death among a population-based cohort of persons living with and without HIV in British Columbia (BC), Canada. Methods: We analysed data from the Comparative Outcomes And Service Utilization Trends (COAST) study; a retrospective population-based study created via linkage between the BC Centre for Excellence in HIV/AIDS and Population Data BC, and containing data for HIV-infected individuals and the general population of BC, respectively. Our analysis included all known HIV-infected adults (≥ 20 years) in BC and a random 10% sample of uninfected BC adults followed from 1996 to 2012. Deaths were identified through Population Data BC – which contains information on all registered deaths in BC (BC Vital Statistics Agency dataset) and classified into cause of death categories using International Classification of Diseases (ICD) 9/10 codes. Age-standardized mortality rates (ASMR) and mortality rate ratios were calculated. Trend test were performed. Results: 3401 (25%), and 47,647 (9%) individuals died during the 5,620,150 person-years of follow-up among 13,729 HIV-infected and 510,313 uninfected individuals, respectively. All-cause and cause-specific mortality rates were consistently higher among HIV-infected compared to HIV-negative individuals, except for neurological disorders. All-cause ASMR decreased from 126.75 (95% CI: 84.92-168.57) per 1000 population in 1996 to 21.29 (95% CI: 17.79-24.79) in 2011-2012 (83% decline; p < 0.001 for trend), compared to a change from 7.97 (95% CI: 7.61-8.33) to 6.87 (95% CI: 6.70-7.04) among uninfected individuals (14% decline; p < 0.001). Mortality rates from HIV/AIDS-related causes decreased by 94% from 103.85 per 1000 population in 1996 to 6.72 by the 2011–2012 era (p < 0.001). Significant ASMR reductions were also observed for hepatic/liver disease and drug abuse/overdose deaths. ASMRs for neurological disorders increased significantly over time. Non-AIDS-defining cancers are currently the leading non-HIV/AIDS-related cause of death in both HIV-infected and uninfected individuals. Conclusions: Despite the significant mortality rate reductions observed among HIV-infected individuals from 1996 to 2012, they still have excess mortality risk compared to uninfected individuals. Additional efforts are needed to promote effective risk factor management and appropriate screening measures among people living with HIV.