Despite evidence supporting the ongoing provision of health education interventions in First Nations communities, there is a paucity of research that specifically addresses how these programs should be designed to ensure sustainability and long-term effects. Using a Community-Based Research approach, a collective case study was completed with three Canadian First Nations communities to address the following research question: What factors are related to sustainable health education programs, and how do they contribute to and/or inhibit program success in an Aboriginal context? Semi-structured interviews and a sharing circle were completed with 19 participants, including members of community leadership, external partners, and program staff and users. Seven factors were identified to either promote or inhibit program sustainability, including: 1) community uptake; 2) environmental factors; 3) stakeholder awareness and support; 4) presence of a champion; 5) availability of funding; 6) fit and flexibility; and 7) capacity and capacity building. Each factor is provided with a working definition, influential moderators, and key evaluation questions. This study is grounded in, and builds on existing research, and can be used by First Nations communities and universities to support effective sustainability planning for community-based health education interventions.