Cooperation, ubiquitous in nature, is difficult to explain from an evolutionary perspective. Many modeling studies strive to resolve this challenge, but their simplifying assumptions on population and interaction structure are rarely met in ecological settings. Here we use a modeling approach that includes more ecological detail to investigate evolution of cooperation in spatially self-organized mussel beds. Mussels cooperate with each other through aggregative movement and attachment using byssal threads. These cooperative behaviors shape the spatial structure of the mussel bed, which can range from scattered distributions to labyrinth-like patterns and dense mussel clumps. The spatial pattern in turn impacts an individual’s fitness at two levels: (i) proper attachment to neighboring individuals decreases predation risk, and (ii) attachment to a sufficiently large group prevents dislodgement by wave stress. Without this second level of selection, our simulations do typically not result in evolutionary attractors that lead to the labyrinth-like spatial patterns that are characteristic for natural mussel beds. Yet, when group-level selection is included, labyrinth-like patterns emerge under a wide range of conditions. Our model demonstrates that multiple selection factors working at different spatial scales – predation of individuals and dislodgement of entire mussel clumps – combinedly determine evolution of cooperative traits in mussels and thereby result in emergence of the labyrinth-like spatial patterns that we observe in natural mussel beds.