Open coal mining causes land degradation, so they need land rehabilitation through re-vegetation programs. The study was conducted in the PT Berau Coal area of Binungan, Lati and Sambarata site, Berau regency, East Kalimantan, Indonesia. Research using a randomized completely block design with the age of re-vegetation as treatments, three replication and three sites as blocks. Sampling unit was selected using a purposive sampling method that is based on the re-vegetation management, including: (i) S1: forest area without mining activities (baseline), (ii) S2: initial re-vegetation, plant age < 1 year, (iii) S3 : medium re-vegetation, plant age 3 years, (iv) further re-vegetation, plant age > 5 years. Soil sample was collected from 0-20 and 20-40 cm soil depth in each treatment at three locations, then analyzed for soil physic and chemistry. Soil of Typic Hapludult on forest land without coal mining has a C-organic (1.87 %), N-total (0.14 %), available-P (31.40 ppm), exchangeable-K (0.11 me/100g), pH (3.98), CEC (10.72 me/100g) and base saturation (17 %). Opened coal mining has led the soil layer becomes exposed and a declining in soil quality drastically. Land closure with the top soil media has been quite able to improve soil properties in rehabilitation areas, but not suitable as media for plant growth, and highly susceptible for further degradation. Land rehabilitation and re-vegetation with fast growing and adaptive pioneer plants such as: Sengon, Acacia, Sungkai, Melina, Angsana, Jarak and Legume Cover Crop (LCC) in the rehabilitation area of coal mining, gave significant effect on the increasing of C-organic, N-total and soil pH. Re-vegetation with fast growing species after 5-year-old has returned the soil chemical properties that are equivalent or even better than thier condition in moist tropical forests without open coal mining.