Ecological theory predicts that animal movement is shaped by its efficiency of resource acquisition. Focusing solely on efficiency, however, ignores the fact that animal activity can affect resource availability and distribution. Here, we show that feedback between individual behavior and environmental complexity can explain movement strategies in mussels. Specifically, experiments show that mussels use a Levy walk during the formation of spatially patterned beds, and models reveal that this Levy movement accelerates pattern formation. The emergent patterning in mussel beds, in turn, improves individual fitness. These results suggest that Levy walks evolved as a result of the selective advantage conferred by autonomously generated, emergent spatial patterns in mussel beds. Our results emphasize that an interaction between individual selection and habitat complexity shapes animal movement in natural systems.