Religious behavior in early childhood plays a crucial role in character formation and emotional regulation. However, its implementation in early childhood education settings often focuses on ritual habituation without optimizing the internalization of religious values. This study aims to analyze the contribution of storytelling the story of Prophet Ayyub (A.S.) to the internalization of religious behavior among children aged 5–6 years and to formulate the conceptual mechanisms underlying this process. The study employed a descriptive qualitative approach at PAUDQ Tarbiyatul Wildan, West Jakarta, involving 15 children, 5 teachers, and 1 principal. Data were collected through observation, semi-structured interviews, and documentation, and analyzed using the Miles and Huberman interactive model. The findings reveal that storytelling the story of Prophet Ayyub (A.S.) contributed to improvements in prayer awareness, participation in simple worship activities, expressions of gratitude, emotional self-control, and patience in social interactions. The study identified three mechanisms of religious value internalization: affective, through children’s emotional engagement with the story character; reflective, through connecting the character’s experiences with the children’s own experiences; and habituative, through reinforcement of values in daily activities. These mechanisms form an integrative model of religious behavior internalization based on prophetic narratives. The findings indicate that storytelling the story of Prophet Ayyub (A.S.) not only strengthens children’s understanding of religious values but also supports the development of emotional regulation and social behavior. Therefore, prophetic storytelling has the potential to serve as an integrative pedagogical approach in Islamic early childhood education.