Twinning is an important mode in plastic deformation of hexagonal close-packed magnesium (Mg) alloys that are promising lightweight structural metals. Recent studies show that the hardness, strength, and stretch formability of Mg alloys can be improved by pre-twinning. However, how twinning and associated microstructure influence the tribological properties of Mg alloys have not been studied systematically. In this work, a gradient twin microstructure in which the density of twins decreases with depth was introduced to an AZ31B Mg alloy plate by laser shock peening. Then sliding tests were performed on surfaces with varying twin volume fraction (TVF) under dry condition. The results shown that both the coefficient of friction (COF) and wear rate decrease with the increase of TVF. A possible mechanism responsible for the effect of surface pre-twinning on the tribo-performance of Mg alloys is proposed. In specific, it is discussed that the improved tribo-performance of Mg alloys by pre-twinning are attributed to the twinning-induced hardening effect, twin growth and saturation phenomenon, and twinning-induced surface crystallographic texture change during sliding. We envision the results in the present study can offer new insights on the designing and developing Mg alloys towards enhanced tribological performance.