The Wind River Elementary Computer Science (WRECS) Collaborative is a research-practice partnership (RPP) among three school districts serving Northern Arapaho and Eastern Shoshone communities on the Wind River Reservation, the Wyoming Department of Education (WDE), [a professional development organization], and [a nonprofit research organization]. The purpose of the WRECS Collaborative is to support development and sustainability of K-8 computer science (CS) education through teacher professional development, leadership capacity-building, and connections to the school and broader communities. The Collaborative has engaged elementary and middle school educators across multiple school years, allowing for exploration of how to build sustainability of CS education across time, particularly in Indigenous communities. In this report, we share strategies the WRECS Collaborative used to foster sustainable CS instruction as we entered our fourth and fifth years of implementation. We share teacher and student survey results that suggest progress toward sustainability, including increases in teacher self-efficacy and perceptions of the feasibility of CS instruction and evidence of developing CS identities in students. We use teacher feedback and interviews to reflect on key features of the RPP’s structure that supported our successes and share future steps we plan to take to address continued challenges.