This study aims to analyze the effectiveness of EduStory-Nature, a digital learning media integrating outdoor education principles, in improving gross motor skills in early childhood, as well as to explore teacher and parent perceptions regarding its implementation. A mixed-methods approach was employed, combining a quasi-experimental design to measure changes in motor skills through pre-test and post-test assessments, and a descriptive qualitative design to examine user acceptability. The research subjects consisted of children aged 4–6 years enrolled in early childhood education (PAUD) institutions in Bandung and Cimahi, while teachers and parents served as supporting informants. The results show a significant improvement in gross motor skills among children who used EduStory-Nature. The N-Gain scores reached the high category, namely 0.72 in PAUD A and 0.68 in PAUD B. In contrast, classes without the media only achieved low N-Gain scores (0.24–0.28). These findings indicate that outdoor-based digital learning provides richer sensory experiences, enhances active body movement, and supports more optimal motor development compared to conventional learning. Qualitative data also reveal a high level of acceptability from teachers and parents in terms of relevance, ease of use, visual attractiveness, and alignment with early childhood developmental needs. Overall, EduStory-Nature is proven to be effective in enhancing gross motor skills and increasing children’s engagement through the integration of narrative, interactive visuals, and nature-based exploration. Its flexibility of implementation—indoors, outdoors, and at home—further strengthens its practicality for early childhood education settings. Keywords: Outdoor Education, Digital Media, Gross Motor Skills, Early Childhood, Edustory-Nature