Abstract Background Although breast-feeding accounts for 15–20% of mother-to-child transmission (MTCT) of HIV, it is not prohibited in some developing countries because of the higher mortality associated with not breast-feeding. We assessed the potential impact, on HIV infection and infant mortality, of a recommendation for shorter durations of exclusive breast-feeding (EBF) and poor compliance to these recommendations. Methods We developed a deterministic mathematical model using primarily parameters from published studies conducted in Uganda or Kenya and took into account non-compliance resulting in mixed-feeding practices. Outcomes included the number of children HIV-infected and/or dead (cumulative mortality) at 2 years following each of 6 scenarios of infant-feeding recommendations in children born to HIV-infected women: Exclusive replacement-feeding (ERF) with 100% compliance, EBF for 6 months with 100% compliance, EBF for 4 months with 100% compliance, ERF with 70% compliance, EBF for 6 months with 85% compliance, EBF for 4 months with 85% compliance Results In the base model, reducing the duration of EBF from 6 to 4 months reduced HIV infection by 11.8% while increasing mortality by 0.4%. Mixed-feeding in 15% of the infants increased HIV infection and mortality respectively by 2.1% and 0.5% when EBF for 6 months was recommended; and by 1.7% and 0.3% when EBF for 4 months was recommended. In sensitivity analysis, recommending EBF resulted in the least cumulative mortality when the a) mortality in replacement-fed infants was greater than 50 per 1000 person-years, b) rate of infection in exclusively breast-fed infants was less than 2 per 1000 breast-fed infants per week, c) rate of progression from HIV to AIDS was less than 15 per 1000 infected infants per week, or d) mortality due to HIV/AIDS was less than 200 per 1000 infants with HIV/AIDS per year. Conclusion Recommending shorter durations of breast-feeding in infants born to HIV-infected women in these settings may substantially reduce infant HIV infection but not mortality. When EBF for shorter durations is recommended, lower mortality could be achieved by a simultaneous reduction in the rate of progression from HIV to AIDS and or HIV/AIDS mortality, achievable by the use of HAART in infants.