Vaginal fistula is a shattering maternal complication characterized by an anomalous opening between the bladder and/or rectum and vagina resulting in continuous leakage of urine or stool. Although prevalent in Ethiopia, its magnitude and distribution is not well studied. We used statistical mapping models using 2005 and 2016 Ethiopia Demographic Health Surveys data combined with a suite of potential risk factors to estimate the burden of vaginal fistula among women of childbearing age. The estimated number of women of childbearing age with lifetime and untreated vaginal fistula in 2016 were 72,533 (95% CI 38,235-124,103) and 31,961 (95% CI 11,596-70,309) respectively. These figures show reduction from the 2005 estimates: 98,098 (95% CI 49,819-170,737) lifetime and 59,114 (95% CI 26,580-118,158) untreated cases of vaginal fistula. The number of districts having more than 200 untreated cases declined drastically from 54 in 2005 to 6 in 2016. Our results show a significant subnational variation in the burden of vaginal fistula. Overall, between 2005 and 2016 there was substantial reduction in the prevalence of vaginal fistula in Ethiopia. Our results help guide local level tracking, planning, spatial targeting of resources and implementation of interventions against vaginal fistula.