Daily oral pre-exposure prophylaxis (PrEP) can safely and effectively prevent HIV acquisition in HIV-negative individuals. However, uptake of PrEP has been suboptimal in sub-Saharan Africa. The goal of this qualitative study was to identify facilitators of and barriers to PrEP acceptability among target users not taking PrEP. Fifty-nine individuals belonging to Ugandan priority populations participated in a single in-depth interview. Participants perceived themselves as being at high risk for HIV acquisition, and expressed interest in PrEP as an HIV prevention strategy. Two forms of stigma emerged as potential barriers to PrEP use: (1) misidentification as living with HIV; and (2) disclosure of membership in a priority population. Acceptability of PrEP was dampened for this sample of potential PrEP users due to anticipated stigmatization. Mitigating stigma should be a key component of effective PrEP delivery to reach UNAIDS goal of ending the AIDS epidemic by 2030.