A fundamental challenge in neuroscience is to understand how biologically salient motor behaviors emerge from properties of the underlying neural circuits. Crayfish, krill, prawns, lobsters, and other long-tailed crustaceans swim by rhythmically moving limbs called swimmerets. Over the entire biological range of animal size and paddling frequency, movements of adjacent swimmerets maintain an approximate quarter-period phase difference with the more posterior limbs leading the cycle. We use a computational fluid dynamics model to show that this frequency-invariant stroke pattern is the most effective and mechanically efficient paddling rhythm across the full range of biologically relevant Reynolds numbers in crustacean swimming. We then show that the organization of the neural circuit underlying swimmeret coordination provides a robust mechanism for generating this stroke pattern. Specifically, the wave-like limb coordination emerges robustly from a combination of the half-center structure of the local central pattern generating circuits (CPGs) that drive the movements of each limb, the asymmetric network topology of the connections between local CPGs, and the phase response properties of the local CPGs, which we measure experimentally. Thus, the crustacean swimmeret system serves as a concrete example in which the architecture of a neural circuit leads to optimal behavior in a robust manner. Furthermore, we consider all possible connection topologies between local CPGs and show that the natural connectivity pattern generates the biomechanically optimal stroke pattern most robustly. Given the high metabolic cost of crustacean swimming, our results suggest that natural selection has pushed the swimmeret neural circuit toward a connection topology that produces optimal behavior.