Natural regeneration of seedlings in mangrove forest is an important part of the secondary succession process. This research aimed to analyze the natural regeneration that occured in degraded areas of Kutai National Park, particularly in Bontang and Sangkima. Data collected was the presence of natural mangrove seedlings and measurement of environmental parameter i.e. soil and sea water. Vegetation inventory was conducted establishing plots placed intentionally (purposive sampling) at rehabilitation plot area of Bontang (0,98 ha) and Sangkima (1,04 ha). Composite soil samples were taken from five points in the plots at two different soil depths: 0-30 cm and 31-61 cm. Water samples of 200 ml were collected from the plots. The results of this study showed that at both locations six species of mangrove seedling were found. Bontang area consist of Acrostichum aureum, Scyphiphora hydrophyllacea, Rhizophora apiculata and also Ceriops tagal species. Meanwhile, in Sangkima area species was identified as: Sonneratia alba, Rhizophora apiculata, and Rhizophora mucronata. Distribution of seedlings mangrove at Bontang area has strong positive correlation with environmental parameter of soil texture (silt and clay), soil chemical (CEC, N, C, Na, Ca), tides, and water chemical (salinity, NO3 and COD). In other hand, seedlings distribution in the Sangkima area have strong positive correlation with environmental parameters of soil texture (sand) and water chemicals (Mg, Al, pH, COD, BOD, DO, and TSS). In order to speed up of the restoration in degraded areas of Kutai National Park mangrove forest, it was need attention to suitability aspects of each species based on the environmental conditions of each site.