BACKGROUND: A key component of malaria elimination campaigns is the identification and targeting of high risk populations. To characterize high risk populations in north central Namibia, a prospective health facility-based case-control study was conducted from December 2012-July 2014. Cases (n = 107) were all patients presenting to any of the 46 health clinics located in the study districts with a confirmed Plasmodium infection by multi-species rapid diagnostic test (RDT). Population controls (n = 679) for each district were RDT negative individuals residing within a household that was randomly selected from a census listing using a two-stage sampling procedure. Demographic, travel, socio-economic, behavioural, climate and vegetation data were also collected. Spatial patterns of malaria risk were analysed. Multivariate logistic regression was used to identify risk factors for malaria. RESULTS: Malaria risk was observed to cluster along the border with Angola, and travel patterns among cases were comparatively restricted to northern Namibia and Angola. Travel to Angola was associated with excessive risk of malaria in males (OR 43.58 95% CI 2.12-896), but there was no corresponding risk associated with travel by females. This is the first study to reveal that gender can modify the effect of travel on risk of malaria. Amongst non-travellers, male gender was also associated with a higher risk of malaria compared with females (OR 1.95 95% CI 1.25-3.04). Other strong risk factors were sleeping away from the household the previous night, lower socioeconomic status, living in an area with moderate vegetation around their house, experiencing moderate rainfall in the month prior to diagnosis and living <15 km from the Angolan border. CONCLUSIONS: These findings highlight the critical need to target malaria interventions to young male travellers, who have a disproportionate risk of malaria in northern Namibia, to coordinate cross-border regional malaria prevention initiatives and to scale up coverage of prevention measures such as indoor residual spraying and long-lasting insecticide nets in high risk areas if malaria elimination is to be realized.