Mining activities lead to extremely harsh environmental conditions, generally reduce soil biodiversity, and limit natural revegetation and ecological restoration. Biotechnological treatments, based on the use of living microorganisms as arbuscular mycorrhizal fungi (AMF), are essential for the recovery of soils degraded by mining. This study was performed in an open-pit gypsum mining site in northwestern Algeria. We compared the effects of three different strategies of AMF inoculation (a commercial AMF inoculum of Rhizophagus irregularis, a native AMF inoculum cultured with leek as nurse plant and a native AMF inoculum made of root fragments and rhizospheric soil from Lavandula spp.) and of one organic amendment. Inoculum were applied at the time of planting of Olea europaea young trees, and the chemical and biological properties of the soil, the structure of the AMF community and the plant physiology were assessed. Two years after plantation, and whatever the AMF treatment, the concentration of the assimilable phosphorus and of the total glomalin-related soil protein has increased into the soil compared to the bare soil. The composition of the AMF community changed and AMF diversity increased over the years regardless of AMF inoculation. This reflects the low presence of AMF in the soil prior to rehabilitation and therefore the benefits of rehabilitation. The highest AMF diversity was measured when using native inoculum. Mineral analysis of O. europaea leaves has revealed an increase in the concentrations of few nutrients including phosphorus when inoculated with a AMF community. Our study participates to show that AMF can promote ecological restoration of mining-impacted sites, by improving soil structure and quality, plant mineral acquisition, and AMF diversity with time.