This study examines the genesis, practice, and Native experiences of stakeholders with two Arizona kindergarten through 12th grade (K-12) statute that mandate instruction of Native American history. The research questions relate to the original intent of the policies, implementation in urban school districts, how Native American parents experienced Native American history in their own education and their aspirations for this type of instruction in their children's education. Lomawaima and McCarty's (2006) safety zone theory was utilized to structure and analyze data. Critical Indigenous Research Methodologies (CIRM) (Brayboy, Gough, Leonard, Roehl, & Solym, 2012; Smith, 2012) was used in this interpretive policy analysis and phenomenological research study. Interviews were conducted with policymakers, a department of education official, urban school district personnel, and Native American parents with children in the pertinent school districts. Data included in-depth interview and legislative committee meeting transcripts, artifacts including bill versions, summaries and fact sheets, school board manuals, and the state social studies standards. The findings indicate that the intent of the statutes was to foster a better understanding among students (and hence, the state's citizenry) leading toward reciprocal government-to-government relationships between tribal nations and non-tribal governments. Teaching sovereignty and self-determination were fundamental. Although the school-based participants had limited knowledge of the policies, the district personnel believed they implemented the mandates because the state social studies standards were utilized to frame instruction. However, the 45 social studies standards related to Native Americans focus on extinct (referred to as historic in the standards) Native societies. The social studies standards ignore contemporary tribal nations and are thus inefficacious in supporting the goal of a better understanding of sovereignty, or in supporting Native American self-determination. The Native parent participants defied stereotypical images; they were involved in their children's educational attainment and were reintroducing cultural and tribal capital. Recommendations include allocating funds to support implementation of the policies at the local school and state levels, establishing culturally responsive curriculum that recognizes and promotes tribal nations and tribal sovereignty, and strengthening relationships between tribal nations, school districts, and the state department of education.