Evidence on the comorbidity between soil-transmitted helminth infections and malaria is scarce and divergent. This study explored the interactions between soil-transmitted helminth infections and uncomplicated falciparum malaria in an endemic area of Colombia. A paired case-control study matched by sex, age and location in Tierralta, Cordoba, was done between January and September 2010. The incident cases were 68 patients with falciparum malaria and 178 asymptomatic controls. A questionnaire was used to gather information on sociodemographic variables. Additionally physical examinations were carried out, stool samples were analysed for intestinal parasites and blood samples for Ig E concentrations. We found associations between infection with hookworm (OR: 4.21; 95% CI: 1.68–11.31) and Ascaris lumbricoides (OR 0.43; 95% CI: 0.18–1.04) and the occurrence of falciparum malaria. The effects of soil-transmitted helminths on the occurrence of malaria were found to be paradoxical. While hookworm is a risk factor, A. lumbricoides has a protective effect. The findings suggest that, in addition to the comorbidity, the presence of common determinants of soil-transmitted helminth infections and malaria could also exist. While the biological mechanisms involved are not clear, public health policies aimed at the control of their common social and environmental determinants are suggested.