Malaria infection starts with injection of Plasmodium sporozoites by an Anopheles mosquito into the skin of the mammalian host. How sporozoites locate and enter a blood vessel is a critical, but poorly understood process. In this study, we examine sporozoite motility and their interaction with dermal blood vessels, using intravital microscopy in mice. Our data suggest that sporozoites exhibit two types of motility: in regions far from blood vessels, they exhibit 'avascular motility', defined by high speed and less confinement, while in the vicinity of blood vessels their motility is more constrained. We find that curvature of sporozoite tracks engaging with vasculature optimizes contact with dermal capillaries. Imaging of sporozoites with mutations in key adhesive proteins highlight the importance of the sporozoite's gliding speed and its ability to modulate adhesive properties for successful exit from the inoculation site.