Vegetation re-establishment is a necessary and critical step in achieving the goal of ecosystem restoration on mined soils. This is especially important because mined soils tend to be a poor medium for plant growth, making natural recolonisation a slow process (Wong, 2003). Native species rehabilitation on mined soils has received much attention, but few studies have correlated native species establishment with mined substrate properties. Currently, a knowledge gap exists in Namibia concerning the physical properties of mined substrates and the suitability of these substrates in supporting plant communities. This study tested the suitability of various mined substrates for the establishment of native savanna species and explored which properties make a particular substrate suitable for plant growth. Seven native savanna species, namely; Acacia senegal, A. tortilis, A. erioloba, A. reficiens, A. erubescens, Catophractes alexandri and Adenolobus garipensis, were selected, and their potential for restoration of mined soils was assessed. The seven species, grown from seeds in the nursery, were transplanted into nine mixtures of substrates at an experimental field site at Navachab Gold Mine, Namibia. Seedling growth and survival were monitored for 40 months. Soil samples of each substrate were analyzed for chemical and physical properties. The highest survival percentage was recorded in Acacia senegal followed by A. erioloba, A. reficiens, A. tortilis, Adenolobus garipensis, Catophractes alexandri and A. erubescens. We suggest that the species survival is determined by its range of tolerance. We found that for most species survival and growth were strongest on calcium and clay substrates. This study showed that species were able to grow outside their natural range of soil conditions, and all the substrates were able to support growth and survival of different species. The survival of the study species was negatively and significantly correlated with sodium and magnesium except for Adenolobus garipensis. The surviving seedlings were well developed and reached a large size in three years. The results suggest that Acacia senegal, Adenolobus garipensis, Acacia tortilis and Acacia erioloba were the most suitable candidates for the restoration of these soils, as they recorded the highest survival and or growth and therefore showed tolerance to extreme soil conditions. Keywords: Mined soils, Establishment, Native species, Substrate properties, Rehabilitation.