Prevalence of HIV-discordance among couples in sub-Saharan Africa is high. Negative partners are at high risk of HIV infection but few HIV/AIDS service providers have developed effective counseling messages for HIV-discordant couples. To identify clients' explanations for discordance, challenges, and prevention strategies, 24 in-depth interviews and 4 focus group discussions were conducted with 32 female and 35 male members of HIV-discordant couples who sought HIV voluntary counseling and testing (VCT) in Uganda. In addition, counselor explanations for discordance were gathered from 62 counselor trainers during 3 interactive workshops. Misconceptions about discordance were widespread among clients and counselors. Common explanations included: the concept of a hidden infection not detectable by HIV tests, belief in immunity, the thought that gentle sex protected HIV-negative partners, and belief in protection by God. Such explanations for discordance reinforced denial of HIV risk for the negative partner within discordant couples and potentially increased transmission risk. Couples identified negotiation of sexual relations as their most formidable challenge. Prevention strategies included condom use, abstinence and separation of beds, contractual agreements for outside sexual partners, and relationship cessation. Discordant couples represent a critical risk group and improved counseling protocols that clearly explain discordance, emphasize high risk of transmission, and support risk reduction are urgently needed.