Gene flow, and resulting degree of genetic differentiation among populations, will shape geographic genetic patterns and possibly local adaptation of parasites and their hosts. Some studies of Plasmodium falciparum in humans show substantial differentiation of the parasite in locations separated by only a few kilometers, a paradoxical finding for a parasite in a large, mobile host. We examined genetic differentiation of the malaria parasite Plasmodium mexicanum, and its lizard host, Sceloporus occidentalis, at 8 sites in northern California, with the use of variable microsatellite markers for both species. These lizards are small and highly territorial, so we expected local genetic differentiation of both parasite and lizard. Populations of P. mexicanum were found to be differentiated by analysis of 5 markers (F_st values >0.05–0.10) over distances as short as 230–400 m, and greatly differentiated (F_st values >0.25) for sites separated by ∼10 km. In contrast, the lizard host had no, or very low, levels of differentiation for 3 markers, even for sites >40 km distant. Thus, gene flow for the lizard was great, but despite the mobility of the vertebrate host, the parasite was locally genetically distinct. This discrepancy could result if infected lizards move little, but their noninfected relatives were more mobile. Previous studies on the virulence of P. mexicanum for fence lizards support this hypothesis. However, changing prevalence of the parasite, without changes in density of the lizard, could also result in this pattern.