The spatio-temporal evolution of Sahelian vegetation is analyzed using the Normalized Difference Vegetation Index (NDVI) obtained from the NOAA/AVHRR sensor (1982--2003). Dominant patterns are identified using rotated EOFs. While the first four modes are associated with specific bio-geo-climatic conditions in space, significant time scales are detected using a multi-tapers method. Three interannual time scales (~6.2-, 4.5- and 3.6-year) are present in the first and third NDVI modes over the western Sahel. A quasi-biennial time scale (~2.6-year) is present in second and fourth NDVI modes over the northeast Sahel. During summer, significant lagged correlations are found between the NDVI second (9-month lag) and third (10-month lag) modes, the meridional Atlantic Sea Surface Temperature (SST) gradient, and the zonal SST gradient in the Indian Ocean. Potential physical linkages and dynamics with known climate fluctuations are discussed.