Evidence suggests substantial declines in HIV prevalence in parts of sub-Saharan Africa. However, the observed aggregate declines at the national level may obscure local variations in the temporal dynamics of the infection. Using spatial scan statistics, we identified marked spatial variability in the within-country declines in HIV prevalence in Tanzania, Malawi, Kenya, and Zimbabwe. Our study suggests that the declines in the national HIV prevalence in some of the SSA countries may not be representative of downward trends in prevalence in areas of high HIV prevalence, as much as the result of sharp declines in prevalence in areas of already low HIV prevalence. Our findings provide insights for resource allocation and HIV prevention interventions in these countries.