Data from the Demographic and Health Surveys for Namibia, Swaziland, and Zambia and the AIDS Indicator Survey from Tanzania were used to examine the influence of marital status and number of partners on consistent condom use among men with casual sexual partnerships in four generalized HIV epidemic settings. We restrict the sample to the 26% (Zambia), 29% (Tanzania), 35% (Swaziland), and 42% (Namibia) of men, who, in the last 12 months before the survey, had any non-marital/non-cohabiting (i.e., casual) sexual partners. We use “condom always used with any partner in the last 12 months” as a dichotomous-dependent measure of consistent condom use. Analyses were stratified by country. Of men with casual partners, 41% (Zambia) to 70% (Namibia) used a condom every time with at least one partner. The majority of men were unmarried/non-cohabiting with one casual partner in the last year. In Swaziland and Zambia, multivariate results suggest that unmarried/non-cohabiting men with one casual partner had significantly lower odds than married/cohabiting men with casual partners to use condoms consistently (odds ratio [OR] = 0.56, p=0.01 and OR = 0.41, p<0.001, respectively.). In Namibia, unmarried/non-cohabiting men with two or more casual partners had significantly greater odds than married/cohabiting men with casual partners to use condoms consistently (OR = 2.80, p<0.01). With some exceptions by country, higher education, religious group, wealth, having no children, knowing HIV results, having an STI, having one lifetime partner, and positive condom knowledge and beliefs also were significantly associated with using a condom every time with any partner. We conclude that consistent condom use remains an elusive goal even among men with casual sexual relationships. Condom use messages should be refined and targeted to men based on their number and types of relationships and combined with other messages to decrease concurrent relationships.