Interface segregation of solute atoms has a profound effect on properties of engineering alloys. In this study, we report a novel strategy for breaking the strength-ductility dilemma of Mg alloy via solute segregation. The hot extruded Mg-1.8Gd-0.3Zr (wt.%) alloy sheet was subjected to three different passes of rolling, and then heat-treated at 200 °C. The high-angle annular dark-field scanning transmission electron microscopy (HAADF-STEM) reveals a remarkable segregation of solute Gd atoms along high and low-angel grain boundaries (GBs). Under almost precipitation-free conditions, the strength and ductility of rolled alloy sheets are simultaneously improved after annealing. Especially for the annealed 3-passes-rolled specimen, the yield strength, ultimate tensile strength, and elongation are simultaneously increased by 11.2%, 7.3%, and 18%, respectively. The solute segregation endows the rolled plate with excellent grain size stability and provides a prominent extra solute cluster strengthening, which completely resists the other softening effects, including dislocation annihilation and grain coarsening during the heating. Meanwhile, the directional migration of Gd atoms and the annihilation of dislocations provide a “clear” space within the grain, which is beneficial for the moving and accumulating of subsequent dislocations. This work sheds light on the solute partitioning behavior and realizes a good application of GB segregation in improving the comprehensive mechanical properties of Mg alloys.