Malaria is frequently diagnosed in urban Kampala, despite low transmission intensity. To evaluate the association between recent travel out of Kampala and malaria, we conducted a matched case–control study. Cases were febrile outpatients with a positive malaria test; controls were febrile outpatients with a negative test. For every two cases, five controls were selected, matching on age. Data were collected on recent overnight travel out of Kampala (past 60 days), destination and duration of travel, and behavioral factors, including sleeping under an insecticide-treated net (ITN) during travel. From July to August 2019, 162 cases and 405 controls were enrolled. The locations of residence of cases and controls were similar. More controls were female (62.7% versus 46.3%, P < 0.001). Overall, 158 (27.9%) participants reported recent overnight travel. Travelers were far more likely to be diagnosed with malaria than those who did not travel (80.4% versus 8.6%, OR 58.9, 95% CI: 23.1–150.1, P < 0.001). Among travelers, traveling to a district not receiving indoor residual spraying of insecticide (OR 35.0, 95% CI: 4.80–254.9, P < 0.001), no ITN use (OR 30.1, 95% CI: 6.37–142.7, P < 0.001), engaging in outdoor activities (OR 22.0, 95% CI: 3.42–141.8, P = 0.001), and age < 16 years (OR 8.36, 95% CI: 2.22–56.2, P = 0.03) were associated with increased odds of malaria. Kampala residents who traveled overnight out of the city were at substantially higher risk of malaria than those who did not travel. For these travelers, personal protection measures, including sleeping under an ITN when traveling, should be advocated.