Background World Health Organization (WHO) guidelines recommend cotrimoxazole prophylaxis for children who are HIV-exposed until infection is excluded and vertical transmission risk has ended. While cotrimoxazole has benefits for children with HIV, there is no mortality benefit for children who are HIV-exposed but uninfected, prompting a review of global guidelines. Here, we model the potential impact of alternative cotrimoxazole strategies on mortality in children who are HIV-exposed. Methods and findings Using a deterministic compartmental model, we estimated mortality in children who are HIV-exposed from 6 weeks to 2 years of age in 4 high-burden countries: Côte d’Ivoire, Mozambique, Uganda, and Zimbabwe. Vertical transmission rates, testing rates, and antiretroviral therapy (ART) uptake were derived from UNAIDS data, trial evidence, and meta-analyses. We explored 6 programmatic strategies: maintaining current recommendations; shorter cotrimoxazole provision for 3, 6, 9, or 12 months; and starting cotrimoxazole only for children diagnosed with HIV. Modelled alternatives to the current strategy increased mortality to varying degrees; countries with high vertical transmission had the greatest mortality. Compared to current recommendations, starting cotrimoxazole only after a positive HIV test had the greatest predicted increase in mortality: Mozambique (961 excess annual deaths; excess mortality 339 per 100,000 HIV-exposed children; risk ratio (RR) 1.06), Uganda (491; 221; RR 1.04), Zimbabwe (352; 260; RR 1.05), and Côte d’Ivoire (125; 322; RR 1.06). Similar effects were observed for 3-, 6-, 9-, and 12-month strategies. Increased mortality persisted but was attenuated when modelling lower cotrimoxazole uptake, smaller mortality benefits, higher testing coverage, and lower vertical transmission rates. The study is limited by uncertain estimates of cotrimoxazole coverage in programmatic settings; an inability to model increases in mortality arising from antimicrobial resistance due to limited surveillance data in sub-Saharan Africa; and lack of a formal health economic analysis. Conclusions Changing current guidelines from universal cotrimoxazole provision for children who are HIV-exposed increased predicted mortality across the 4 modelled high-burden countries, depending on test-to-treat cascade coverage and vertical transmission rates. These findings can help inform policymaker deliberations on cotrimoxazole strategies, recognising that the risks and benefits differ across settings.