This study employs landscape genetics to investigate the environmental drivers of a deadly vector-borne disease, malaria caused by Plasmodium falciparum, in a more spatially comprehensive manner than any previous work. With 1,804 samples from 44 sites collected in western Kenya in 2012 and 2013, we performed resistance surface analysis to show that Lake Victoria acts as a barrier to transmission between areas north and south of the Winam Gulf. In addition, Mantel correlograms clearly showed significant correlations between genetic and geographic distance over short distances (< 70 km). In both cases, we used an identity-by-state measure of relatedness tailored to highly-related individuals in order to focus on recent gene flow that is more relevant to transmission. To supplement these results, we also performed conventional population genetics analyses, including Bayesian clustering methods and spatial ordination techniques. These revealed some differentiation on the basis of geography and elevation and a cluster of genetic similarity in the lowlands north of the Winam Gulf of Lake Victoria. Taken as a whole, these results indicate low overall genetic differentiation in the Lake Victoria region, but with some separation of populations north and south of the Winam Gulf that is explained by the presence of the lake as a geographic barrier to gene flow. We recommend similar landscape genetics analyses in future molecular epidemiology studies of vector-borne diseases to extend and contextualize the results of traditional population genetics.