The formability and mechanical properties of many engineering alloys are intimately related to the formation and growth of twins. Understanding the structure and chemistry of twin boundaries at the atomic scale is crucial if we are to properly tailor twins to achieve a new range of desired properties. We report an unusual phenomenon in magnesium alloys that until now was thought unlikely: the equilibrium segregation of solute atoms into patterns within fully coherent terraces of deformation twin boundaries. This ordered segregation provides a pinning effect for twin boundaries, leading to a concomitant but unusual situation in which annealing strengthens rather than weakens these alloys. The findings point to a platform for engineering nano-twinned structures through solute atoms. This may lead to new alloy compositions and thermomechanical processes.