BACKGROUND: Assisted partner services (aPS) or provider notification for sexual partners of persons diagnosed HIV-positive can increase HIV testing and linkage in sub-Saharan Africa (SSA) and is a high yield strategy to identify HIV-positive persons. However, its cost-effectiveness is not well-evaluated. METHODS: Using effectiveness and cost data from an aPS trial in Kenya, we parameterized an individual-based, dynamic HIV transmission model. We estimated costs for both a program scenario and a task-shifting scenario using community health workers to conduct the intervention. We simulated 200 cohorts of 500,000 individuals and projected the health and economic effects of scaling up aPS in a region of western Kenya (formerly Nyanza Province). FINDINGS: Over a 10-year time horizon with universal ART initiation, implementing aPS in western Kenya was projected to reach 12.5% of the population and reduce incident HIV infections by 3.7%. In sexual partners receiving aPS, HIV-related deaths were reduced by 13.7%. The incremental cost-effectiveness ratio (ICER) of aPS was $1,094 USD (90% model variability $823-1,619) and $833 (90% model variability $628-1,224) per disability-adjusted life year (DALY) averted under the program and task-shifting scenario, respectively. The ICERs for both scenarios fall below Kenya's gross domestic product (GDP) per capita ($1,358) and are therefore considered very cost-effective. Results were robust to varying healthcare costs, linkage to care rates, partner concurrency rates, and ART eligibility thresholds (</=350 cells/uL, </=500 cells/uL, and universal ART). INTERPRETATION: APS is cost-effective for reducing HIV-related morbidity and mortality in western Kenya and similar settings. Task-shifting can increase program affordability.