Despite widespread messaging supporting male (external) condom use to prevent HIV in endemic settings, utilization of condoms is low across sub-Saharan Africa. A thorough understanding of barriers to condom use as a form of HIV prevention is necessary to reduce HIV transmission. Here, we present qualitative data from rural eastern Africa to explain low utilization of condoms among heterosexual adults. Focus groups and interviews were conducted in Tanzania and Uganda between 2016 and 2019. A content analysis approach was used to identify attitudes about condoms and factors related to use/non-use. We found that strategies such as abstinence and being faithful to one's partner are perceived as ideal but rarely achievable methods of HIV prevention. Condoms are used in the setting of "failure" to abstain or be faithful and are therefore stigmatized as markers of infidelity. As such, use within cohabiting and long-term relationships is low. Our data suggest that negative perceptions of condoms may stem from persistent effects of the formerly applied "ABC" HIV prevention approach, a public health messaging strategy that described A-abstinence, B-be faithful, and C-use a condom as tiered prevention tools. Condom uptake could increase if HIV prevention messaging acknowledges existing stigma and reframes condom use for proactive health prevention. These studies were approved by Weill Cornell Medicine (Protocols 1803019105 and 1604017171), Mbarara University of Science and Technology (Protocol 16/0117), Uganda National Council of Science and Technology (Protocol SS-4338), and the Tanzania National Institute for Medical Research (Protocol NIMR/HQ/R.8c/Vol.I/1330).