Spatio-temporal vegetation cover change has been a pressing issue in Botswana since the twentieth century. However, due to the country’s semi-arid characteristics, vegetation cover varies greatly, increasing significantly with changing climate; hence, the magnitude of the cover change is also highly variable. Monitoring vegetation cover change is hence crucial for better ecosystem management practices. This study utilized the Normalized Vegetation Index (NDVI) from Advanced Very High-Resolution Radiometer (AVHRR) satellite to assess the spatio-temporal variability of vegetation cover in Botswana using AHVRR NDVI multitemporal time series data from 1982 to 2015. Biweekly datasets were aggregated to monthly composites using the Maximum Value Composite (MVC) and then later to annual composites. A pixelwise analysis was adopted to determine areas of constant positive trends (greening) and areas of constant negative trends (browning). The findings of the study indicate that 93%, 89% and 89% of the spatial trends were significant for linear regression, Mann–Kendall and Sen’s slope, respectively, at α = 0.05. Furthermore, the study revealed a significant (p value = 0.01, tau = 0.08214096, Sen’s slope = 0.00007) upwards annual temporal trend. The results of the present study are expected to inform decision-making and management strategies for vegetation monitoring under a changing climate in Botswana and sub-Saharan Africa.