A recent randomized controlled trial shows a significant reduction in women-to-men transmission of HIV due to male circumcision. Such development calls for a rigorous mathematical study to ascertain the full impact of male circumcision in reducing HIV burden, especially in resource-poor nations where access to anti-retroviral drugs is limited. First of all, this paper presents a compartmental model for the transmission dynamics of HIV in a community where male circumcision is practiced. In addition to having a disease-free equilibrium, which is locally-asymptotically stable whenever a certain epidemiological threshold is less than unity, the model exhibits the phenomenon of backward bifurcation, where the disease-free equilibrium coexists with a stable endemic equilibrium when the threshold is less than unity. The implication of this result is that HIV may persist in the population even when the reproduction threshold is less than unity. Using partial data from South Africa, the study shows that male circumcision at 60% efficacy level can prevent up to 220,000 cases and 8,200 deaths in the country within a year. Further, it is shown that male circumcision can significantly reduce, but not eliminate, HIV burden in a community. However, disease elimination is feasible if male circumcision is combined with other interventions such as ARVs and condom use. It is shown that the combined use of male circumcision and ARVs is more effective in reducing disease burden than the combined use of male circumcision and condoms for a moderate condom compliance rate.