A deterministic model for the co-interaction of HIV and malaria in a community is presented and rigorously analyzed. Two sub-models, namely the HIV-only and malaria-only sub-models, are considered first of all. Unlike the HIV-only sub-model, which has a globally-asymptotically stable disease-free equilibrium whenever the associated reproduction number is less than unity, the malaria-only sub-model undergoes the phenomenon of backward bifurcation, where a stable disease-free equilibrium co-exists with a stable endemic equilibrium, for a certain range of the associated reproduction number less than unity. Thus, for malaria, the classical requirement of having the associated reproduction number to be less than unity, although necessary, is not sufficient for its elimination. It is also shown, using centre manifold theory, that the full HIV-malaria co-infection model undergoes backward bifurcation. Simulations of the full HIV-malaria model show that the two diseases co-exist whenever their reproduction numbers exceed unity (with no competitive exclusion occurring). Further, the reduction in sexual activity of individuals with malaria symptoms decreases the number of new cases of HIV and the mixed HIV-malaria infection while increasing the number of malaria cases. Finally, these simulations show that the HIV-induced increase in susceptibility to malaria infection has marginal effect on the new cases of HIV and malaria but increases the number of new cases of the dual HIV-malaria infection.