We describe two Malawian adults on successful antiretroviral therapy who experienced frequent malaria episodes after stopping cotrimoxazole prophylaxis. We argue that, in addition to stopping cotrimoxazole, diminished malaria immunity and drug interactions between efavirenz and artemether-lumefantrine may have played a causative role in the recurrent malaria our patients experienced.