To adapt to their environments, animals must generate behaviors that are closely aligned to a rapidly changing sensory world. However, behavioral states such as foraging or courtship typically persist over long time scales. It remains unclear how neural circuits generate persistent behavioral states while maintaining flexibility to switch states when the context changes. Here, we elucidate the architecture of a circuit controlling the choice between roaming and dwelling foraging states in C. elegans. Through ensemble-level calcium imaging in freely-moving animals, we identify stable, circuit-wide activity patterns corresponding to each state. Mutual inhibition between two neuromodulatory systems underlies the persistence and mutual exclusivity of the opposing network states. We identify a sensory processing neuron that transmits information about food odors to both the roaming and dwelling circuits, biasing the animal towards different states in different contexts. These findings reveal a circuit architecture that enables flexible, sensory-driven control of persistent behavioral states.