BACKGROUND: Stigma and discrimination related to HIV and key populations at high risk of HIV have the potential to impede the implementation of effective HIV prevention and treatment programmes at scale. Studies measuring the impact of stigma on these programmes are rare. We are conducting an implementation science study of HIV-related stigma in communities and health settings within a large, pragmatic cluster-randomized trial of a universal testing and treatment intervention for HIV prevention in Zambia and South Africa and will assess how stigma affects, and is affected by, implementation of this intervention. METHODS/DESIGN: A mixed-method evaluation will be nested within HIV prevention trials network (HPTN) 071/PopART (Clinical Trials registration number NCT01900977), a three-arm trial comparing universal door-to-door delivery of HIV testing and referral to prevention and treatment services, accompanied by either an immediate offer of anti-retroviral treatment to people living with HIV regardless of clinical status, or an offer of treatment in-line with national guidelines, with a standard-of-care control arm. The primary outcome of HPTN 071/PopART is HIV incidence measured among a cohort of 52 500 individuals in 21 study clusters. Our evaluation will include integrated quantitative and qualitative data collection and analysis in all trial sites. We will collect quantitative data on indicators of HIV-related stigma over 3 years from large probability samples of community members, health workers and people living with HIV. We will collect qualitative data, including in-depth interviews and observations from members of these same groups sampled purposively. In analysis, we will: (1) compare HIV-related stigma measures between study arms, (2) link data on stigma to measures of the success of implementation of the PopART intervention and (3) explore changes in the dominant drivers and manifestations of stigma in study communities and the health system. DISCUSSION: HIV-related stigma may impede the successful implementation of HIV prevention and treatment programmes. Using a novel study-design nested within a large, community randomized trial we will evaluate the extent to which HIV-related stigma affects and is affected by the implementation of a comprehensive combination HIV prevention intervention including a universal test and treatment approach.