Vegetation assessments are critical in the status and success of reintroduction programs and are an important aspect in ecological restoration. Vegetation structure and composition influences the suitability and availability of unique habitats for different wildlife species. The objectives of this study were to (1) establish the vegetation structure and composition, and (2) determine the soil-vegetation associations in southern Umfurudzi Park, Zimbabwe, prior to the reintroduction of wildlife species. Using a stratified random design, 15 rectangular plots from three strata were assessed in April and May 2012. A total of 23 woody plants from 58 tree and 68 shrub families as well as 30 grass species were recorded. Tree basal area, canopy cover, tree density, tree and grass species diversity, and tree height for the riverine strata were significantly different from the miombo and vlei strata. The influence of soil properties on the occurrence and diversity of woody and grass species was evident across the three strata. Long-term changes in the vegetation dynamics and primary productivity in southern Umfurudzi Park due to the reintroduced mega-herbivores is recommended for the success of the restoration program.