How individuals move through their environment dictates which other individuals they encounter, determining their social and reproductive interactions and the extent to which they experience sexual selection. Specifically, females rarely have the option of mating with all males in a population—they can only choose among the males they encounter. Further, quantifying phenotypic differences between the males that females encounter and those that sire females’ offspring lends insight into how social and reproductive interactions shape male phenotypes. We used an explicitly spatiotemporal Markov chain model to estimate the number of potential mates of Anolis sagrei lizards from their movement behavior, and used genetic paternity assignments to quantify sexual selection on males. Females frequently encountered and mated with multiple males, offering ample opportunity for female mate choice. Sexual selection favored males that were bigger and moved over larger areas, though the effect of body size cannot be disentangled from last-male precedence. Our approach corroborates some patterns of sexual selection previously hypothesized in anoles based on describing them as territorial, whereas other results, including female multiple mating itself, are at odds with territorial polygyny, offering insight into discrepancies in other taxa between behavioral and genetic descriptions of mating systems.