The spatial extent of desertified vs. rehabilitated areas in the Mu Us Sandy Land, China, was explored. The area is characterized by complex landscape changes that were caused by different drivers, either natural or anthropogenic, interacting with each other, and resulting in multiple consequences. Two biophysical variables, NDVI, positively correlated with vegetation cover, and albedo, positively correlated with cover of exposed sands, were computed from a time series of merged NOAA-AVHRR and MODIS images (1981 to 2010). Generally, throughout the study period, NDVI increased and albedo decreased. Improved understanding of spatial and temporal dynamics of these environmental processes was achieved by using the Change Vector Analysis (CVA) technique applied to NDVI and albedo data extracted from four sets of consecutive Landsat images, several years apart. Changes were detected for each time step, as well as over the entire period (1978 to 2007). Four categories of land cover were created—vegetation, exposed sands, water bodies and wetlands. The CVA’s direction and magnitude enable detecting and quantifying finer changes compared to separate NDVI or albedo difference/ratio images and result in pixel-based maps of the change. Each of the four categories has a biophysical meaning that was validated in selected hot-spots, employing very high spatial resolution images (e.g., Ikonos). Selection of images, taking into account inter and intra annual variability of rainfall, enables differentiating between short-term conservancies (e.g., drought) and long-term alterations. NDVI and albedo, although comparable to tasseled cap’s brightness and greenness indices, have the advantage of being computed using reflectance values extracted from various Landsat platforms since the early 1970s. It is shown that, over the entire study period, the majority of the Mu Us Sandy Land area remained unchanged. Part of the area (6%), mainly in the east, was under human-induced rehabilitation processes, in terms of increasing vegetation cover. In other areas (5.1%), bare sands were found to expand to the central-north and the southwest of the area.