Various media reported about poor child's behavior lately. Some violence committed by children to their own friends, lack of respect to parents and teachers, shows child’s bad character. It inspires the writer to dig back cultures that was used as a media of character building for children by their parents long ago. Bali communities has a variety of culture that can be used as a media of character education, such as storytelling culture for children, the story is believed to contain values of character education for children from an early age. The purpose of this paper is to explore values of characters that can be transferred through story of Pedanda Baka and how this story can be used as media of character education to children at an early age. This article is a review of the literature. After assessment, we found that character that can be educated through Pedanda Baka story is religious character. Character education through Pedanda Baka story was done by telling story to children by parents at home and by teachers at school because cognitive development of early childhood is a symbolic behavior, and the story is symbolic. Stories help abstract and intangible concept becomes concrete and tangible. Story can be used as a media of character education since early childhood, because it helps children imitate religious character in the story.