Sub-Saharan Africa (SSA) is the region with the world’s highest rates of HIV and other sexually transmissible infections (STIs), yet numerous studies show that condom use is generally rare. This suggests a need for a better understanding of how condoms fit within sexual practices and relationships in SSA. This paper seeks to address this need by reviewing research published between the late 1980s and 2011 on use and factors influencing use of male condoms in SSA. What is evident from this research is that condom use involves complex social and interpersonal dynamics, with structural and cultural conditions exerting an influence through framing social cognitions and setting boundaries on autonomy that make the apparently irrational choice of eschewing condoms a rational decision. The influences of poverty; relationships with parents, peers and partners; limited, insufficient or absent information especially in rural areas and among men who have sex with men; gender and sexual norms, and the dynamics of gendered power; and beliefs and attitudes about HIV, condoms and sexuality all have been shown to work against condom use for a large proportion of Africa’s people. However, promising results are shown in trends towards increased condom use among single women in numerous countries, increasing acceptance and use of condoms among some university students, successes in producing potentially sustainable condom use resulting from select interventions, and resistance to succumbing to the dominant gender–power dynamics and structural–cultural impediments that women in groups have mobilised.