Objectives. To assess a healthy retail intervention in Tribal convenience stores in Oklahoma. Methods. We adapted healthy retail strategies to the context of 8 Tribally owned stores. We assessed individual- and store-level outcomes in a cluster-controlled intervention trial (April 2016–June 2017). We measured fruit and vegetable intake, store environment perceptions, and purchases before and after the intervention among a cohort of 1637 Native American shoppers. We used mixed-effects linear regression to estimate pre- to postintervention changes in and between groups. Results. We followed 74% of participants (n = 1204) 9 to 12 months. Intervention and control participants perceived healthier stores after intervention. Higher shopping frequency was related to purchases of fruits, vegetables, and healthy items. Conclusions. Intervention exposure was associated with healthy purchasing but not fruit and vegetable intake. Research is needed to further assess impacts of environmental interventions on intake. Public Health Implications. As the first healthy retail intervention in Tribally owned stores, our results contribute evidence for environmental and policy interventions to address obesity in Tribal Nations. Multicomponent interventions, led by Tribal leaders from diverse sectors, are needed to create healthy environments and sustainable improvements in Native American health.