While sensory coding is traditionally thought of as a process independent of behavioral state, modern studies showcase potent modulatory effects of movement on sensory neurons. Intriguingly, these effects are not uniform and can differ between species. In insects and rodents, visual responses increase dramatically when the animal is moving, whereas in primates locomotion has a weak impact on responses in the primary visual cortex (V1). These differences raise questions about the existence and universality of computational principles underlying sensory coding during behavior. We take a normative perspective and consider how locomotion should optimally modulate sensory neurons. Our approach is based on the efficient coding hypothesis, which postulates that sensory systems exploit the statistics of natural stimuli to maximize information transmission under a variety of constraints. To determine how sensory inputs change with locomotion, we recorded videos of natural scenes with a stationary and moving camera. We processed these videos with filters designed to mimic the receptive fields of rodent and primate V1 and identified significant differences between movement states and species. While locomotion increased the dynamic range of responses of large, low-frequency filters reminiscent of mouse V1, the outputs of small, high-frequency filters matching primate V1 did not change significantly with movement. To understand how the brain should adjust to these changes in stimulus statistics, we developed a model of neurons that are modulated by locomotion to efficiently encode inputs that change systematically with running speed. We found that optimally modulated neurons qualitatively reproduce a range of phenomena observed in mouse and primate V1 during behavior. Our approach indicates that the seemingly disparate effects of locomotion on sensory coding throughout the animal kingdom may share a common, general principle: neurons adjust their properties to maintain accurate information transmission across different environments and behavioral states.