Controlling aeolian desertification is a key ecological target on the Tibetan Plateau, especially within the widespread river valleys. Vegetation recovery can change the near-soil surface characteristics, which thus may influence wind erodibility of soils. However, these potential effects are not sufficiently evaluated for aeolian sandy soils. This study selected the Shannan valley of the Yarlung Zangbo River on the southern Tibetan Plateau as a case to investigate the variations in wind erodibility of aeolian sandy soils impacted by different vegetation restoration, since many ecological measures have been implemented in recent decades in the river valley. Eight vegetated sandy lands with different restoration types and ages and two bare sandy lands (as controls) were chosen as test sites. Four vegetated sandy lands were covered by Artemisia wellbyi, Hedysarum scoparium, Sophora moorcroftiana, and Populus L. with the similar restoration age of 10 years. For Sophora moorcroftiana and Populus L. communities, two restoration ages of 6 and over 30 years were also selected respectively. Wind erodibility was reflected by wind erodible fraction (EF), mean weight diameter of dry aggregates (MWD), capillary water capacity (CWC), soil cohesion (CS), and soil penetration resistance (PR) from different aspects. A comprehensive wind erodibility index (CWEI) was further produced by a weighted summation method to combine those five indices together and comprehensively quantify the effects of vegetation restoration on wind erodibility of aeolian sandy soils. The results showed that revegetation was efficient to reduce wind erodibility of aeolian sandy soils. EF generally decreased, while MWD, CWC, CS, and PR increased after vegetation restoration on the aeolian sandy lands. The CWEI of vegetated sandy lands varied greatly from 0.850 to 0 under different restoration types and ages and decreased by 14.4% to 100% compared to the control. Under the four different restoration types, Populus L. had the relatively minimum CWEI, followed by Artemisia wellbyi, Sophora moorcroftiana and Hedysarum scoparium. With succession from 6 to over 30 years, CWEI gradually declined for both the Populus L. and Sophora moorcroftiana restored sandy lands. The decreases in wind erodibility (reflected by CWEI) on vegetated sandy lands were dominantly controlled by the improvement of soil texture and the increases of organic matter and calcium carbonate contents with vegetation restoration. The combined vegetation measure of Populus L. mixed with shrubs and grasses was suggested as the optimal restoration type for mitigating wind erodibility of aeolian sandy soils in the Shannan valley of the Yarlung Zangbo River.