HIV counselling and testing (HTC) is an integral component of HIV preventive strategies. Despite an increase in the number of HTC sites, HIV testing uptake among young women in Tanzania is relatively low compared to other countries in Sub-Saharan Africa. This study aimed to explore the factors associated with changes in HIV testing uptake using Tanzania HIV/AIDS and Malaria Indicator Surveys of 2003-04, 2007-08 and 2011-12. This was a secondary data analysis using the 2003-04 Tanzanian HIV/AIDS Indicator Survey (THIS), and the 2007-08 and 2011-12 Tanzanian HIV/AIDS and Malaria Indicator Surveys (THMIS). The study population consisted of young women 15 – 24 years old at the time of each survey. Using a pooled logistic regression we identified factors associated with HIV testing uptake during the study period. Multivariate decomposition analysis was used to assess factors associated with the changes in HIV testing uptake over the survey period. HIV testing uptake among this population was 6.6%, 30.8% and 39.8% for 2003-04, 2007-08 and 2011-12 surveys respectively. Independent of other covariates, the time period of the survey has an important effect on uptake of HIV testing. Women’s age (20- 24 years), education level (primary & secondary), ever married, number of life sex partners (1 or more),having STI or symptoms of STI and attendance to antenatal care were significantly associated with higher odds of HIV testing across both sets of pooled surveys. Changes in characteristics of the sub-populations (endowments) in 2003-04 vs 2007-08 surveys would have resulted in low HIV testing uptake (-5.26%) in the absence of the changes in effects of these characteristic which contributed most of the changes in HIV testing uptake; (105.26%). In 2007-08 vs 2011-12 surveys, the changes in endowments contributed to 21.1% of the changes in HIV testing uptake, while 77.9% of the changes were attributed to coefficients. Both endowments and coefficients were statistically significant in both of the multivariate decomposition models. HIV testing has been greater among women with high risk factors, and thus has become more targeted. Until testing is universal, an effective expansion strategy would be to prioritize those most likely to be infected.