This paper uses data from a community cross-sectional survey to examine the factors that are associated with justification of physical violence against women. Results indicate that respondents who were married at the time of the survey were less likely (OR = 0.29; CI = 0.17–0.52) to agree that it is justified for a man to physically assault his partner that their counterparts who were single. The likelihood to justify physical violence was less likely to happen among respondents with primary education (OR = 0.49; CI = 0.39–0.62), secondary education (OR = 0.40; CI = 0.31–0.53) and vocation or tertiary education (OR = 0.28; CI = 0.19–0.41) than among respondents with no education. Protestants were less likely (OR = 0.77; CI = 0.64–0.94) to justify physical violence than the Catholics. Respondents who were not formally employed were more likely (OR = 1.66; CI = 1.32–2.08) to justify physical violence than their counterparts who were in formal employment in the last three months preceding the survey. Respondents who agreed that it is okay for a man to control his partner’s movements (OR = 1.27; CI = 1.04–1.55), it is okay for a man to have sex with his wife anytime (OR = 2.28; CI = 1.87–2.78), alcohol is the main reason for violence against women (OR = 1.67; CI = 1.33–2.10), men need sex more than women (OR = 1.57; CI = 1.23–1.99) and women know where to obtain support in case of violence (OR = 1.42; CI = 1.00–2.02) were more likely to justify physical violence than respondents who disagreed. The likelihood to justify physical violence was less among respondents who agreed that: violence is not the only way to deal with disagreements (OR = 0.54; CI = 0.33–0.86), it is possible for men to stop violence (OR = 0.62; CI = 0.47–0.82) and it is acceptable for a woman to ask her partner to use a condom (OR = 0.61; CI = 0.51–0.73) than their counterparts who disagreed. There is need to increase investment in social norms change programmes in order to strengthen contestation of tolerance of physical violence among men and women in Uganda.