We conducted a qualitative analysis to evaluate the acceptability of using storytelling as a way to communicate oral health messages regarding early childhood caries (ECC) prevention in the American Indian and Alaska Native (AIAN) population.A traditional story was developed and pilot tested among AIAN mothers residing in 3 tribal locations in northern California. Evaluations of the story content and acceptability followed a multistep process consisting of initial feedback from 4 key informants, a focus group of 7 AIAN mothers, and feedback from the Community Advisory Board. Upon story approval, 9 additional focus group sessions (N = 53 participants) were held with AIAN mothers following an oral telling of the story.Participants reported that the story was culturally appropriate and used relatable characters. Messages about oral health were considered to be valuable. Concerns arose about the oral-only delivery of the story, story content, length, story messages that conflicted with normative community values, and the intent to target audiences. Feedback by focus group participants raised some doubts about the relevance and frequency of storytelling in AIAN communities today.AIAN communities value the need for oral health messaging for community members. However, the acceptability of storytelling as a method for the messaging raises concerns, because the influence of modern technology and digital communications may weaken the acceptability of the oral tradition. Careful attention must be made to the delivery mode, content, and targeting with continual iterative feedback from community members to make these messages engaging, appropriate, relatable, and inclusive.