Mosquitoes are prolific disease vectors that affect public health around the world. Although many studies have investigated search strategies used by host-seeking adult mosquitoes, little is known about larval search behavior. Larval behavior affects adult body size and fecundity, and thus the capacity of individual mosquitoes to find hosts and transmit disease. Understanding vector survival at all life stages is crucial for improving disease control. In this study we use experimental and computational methods to investigate the chemical ecology and search behavior of Aedes aegypti mosquito larvae. We first show that larvae do not respond to several olfactory cues used by adult Ae. aegypti to assess larval habitat quality, but perceive microbial RNA as a potent foraging attractant. Second, we demonstrate that Ae. aegypti larvae use chemokinesis, an unusual search strategy, to navigate chemical gradients. Finally, we use computational modeling to demonstrate that larvae respond to starvation pressure by optimizing exploration behavior - possibly critical for exploiting limited larval habitat types. Our results identify key characteristics of foraging behavior in an important disease vector mosquito. In addition to implications for better understanding and control of disease vectors, this work establishes mosquito larvae as a tractable model for chemosensory behavior and navigation.