INTRODUCTION: Previous unblinded trials have shown increased malaria among HIV-infected adults on antiretroviral therapy (ART) who stop cotrimoxazole (CTX) prophylaxis. We investigated the effect of stopping CTX on malaria in HIV-infected adults on ART in a double-blind, placebo-controlled trial. METHODS: HIV-infected Ugandan adults stable on ART and CTX with CD4 cell count at least 250 cells/μl were randomized (1 : 1) to continue CTX or stop CTX and receive matching placebo (COSTOP trial; ISRCTN44723643). Clinical malaria was defined as fever and a positive blood slide, and considered severe if a participant had at least one clinical or laboratory feature of severity or was admitted to hospital. Malaria incidence and rate ratios were estimated using random effects Poisson regression, accounting for multiple episodes. RESULTS: A total of 2180 participants were enrolled and followed for a median of 2.5 years; 453 malaria episodes were recorded. Malaria incidence was 9.1/100 person-years (pyrs) [95% confidence interval (CI) = 8.2-10.1] and was higher on placebo (rate ratio 3.47; CI = 2.74-4.39). Malaria in the placebo arm decreased over time; although incidence remained higher than in the CTX arm, the difference between arms reduced slightly (interaction P value = 0.10). Fifteen participants experienced severe malaria (<1%); overall incidence was 0.30/100 pyrs (CI = 0.18-0.49). There was one malaria-related death (CTX arm). CONCLUSION: HIV-infected adults - who are stable on ART and stop prophylactic CTX - experience more malaria than those that continue, but this difference is less than has been reported in previous trials. Few participants had severe malaria. Further research might be useful in identifying groups that can safely stop CTX prophylaxis.