The authors tested the effectiveness of a community-based, tribally delivered oral health promotion (OHP) intervention (INT) at reducing caries increment in Navajo children attending Head Start. In a 3-y cluster-randomized trial, we developed an OHP INT with Navajo input that was delivered by trained Navajo lay health workers to children attending 52 Navajo Head Start classrooms (26 INT, 26 usual care [UC]). The INT was designed as a highly personalized set of oral health-focused interactions (5 for children and 4 for parents), along with 4 fluoride varnish applications delivered in Head Start during academic years of 2011 to 2012 and 2012 to 2013. The authors evaluated INT impact on decayed, missing, and filled tooth surfaces (dmfs) increment compared with UC. Other outcomes included caries prevalence and caregiver oral health-related knowledge and behaviors. Modified intention-to-treat and per-protocol analyses were conducted. The authors enrolled 1,016 caregiver-child dyads. Baseline mean dmfs/caries prevalence equaled 19.9/86.5% for the INT group and 22.8/90.1% for the UC group, respectively. INT adherence was 53% (i.e., [greater than or equal to] 3 child OHP events, [greater than or equal to] 1 caregiver OHP events, and [greater than or equal to] 3 fluoride varnish). After 3 y, dmfs increased in both groups (+12.9 INT vs. +10.8 UC; P = 0.216), as did caries prevalence (86.5% to 96.6% INT vs. 90.1% to 98.2% UC; P = 0.808) in a modified intention-to-treat analysis of 897 caregiver-child dyads receiving 1 y of INT. Caregiver oral health knowledge scores improved in both groups (75.1% to 81.2% INT vs. 73.6% to 79.5% UC; P = 0.369). Caregiver oral health behavior scores improved more rapidly in the INT group versus the UC group (P = 0.006). The dmfs increment was smaller among adherent INT children (+8.9) than among UC children (+10.8; P = 0.028) in a per-protocol analysis. In conclusion, the severity of dental disease in Navajo Head Start children is extreme and difficult to improve. The authors argue that successful approaches to prevention may require even more highly personalized approaches shaped by cultural perspectives and attentive to the social determinants of oral health (ClinicalTrials.gov NCT01116739). (author abstract)