The surface of Mars has changed dramatically during the three decades spanned by spacecraft exploration. Comparisons of Mars Global Surveyor images with Viking and Mariner 9 pictures suggest that more than one third of Mars' surface area has brightened or darkened by at least 10%. Such albedo changes could produce significant effects on solar heating and the global circulation of winds across the planet. All of the major changes took place in areas of moderate to high thermal inertia and rock abundance, consistent with burial of rocky surfaces by thin dust layers deposited during dust storms and subsequent exposure of the rocky surfaces by aeolian erosion. Several distinct mechanisms contribute to aeolian erosion on Mars. Persistent winds dominate erosion at low latitudes, producing diffuse albedo boundaries and linear wind streaks generally oriented in the direction of southern summer winds. Dust devils darken the mid- to high- latitudes from 45 to 70 degrees during the summer seasons, forming irregular albedo patterns consisting of dark linear tracks. Dust storms produce regional albedo variations with distinct but irregular margins. Dark sand dunes in southern high latitudes appear to be associated with regional darkening that displays diffuse albedo boundaries. No surface changes were observed to repeat regularly on an annual basis, but many of the changes took place in areas that alternate episodically between high and low albedo states as thin mantles of dust are deposited and later stripped off. Hence, the face of Mars remains recognizable after a century of telescopic observations, in spite of the enormous extent of alteration that has taken place during the intervals between spacecraft missions.