Arsenic is a naturally occurring toxicant in groundwater, which increases cancer and cardiovascular disease risk. American Indian populations are disproportionately exposed to arsenic in drinking water. The Strong Heart Water Study (SHWS), through a community-centered approach for intervention development and implementation, delivered an arsenic mitigation program for private well users in American Indian communities. The SHWS program comprised community-led water arsenic testing, point-of-use arsenic filter installation, and a mobile health program to promote sustained filter use and maintenance (i.e., changing the filter cartridge). Half of enrolled households received additional in-person behavior change communication and videos. Our objectives for this study were to assess successes, barriers, and facilitators in the implementation, use, and maintenance of the program among implementers and recipients. We conducted 45 semi-structured interviews with implementers and SHWS program recipients. We analyzed barriers and facilitators using the Consolidated Framework for Implementation Research and the Risks, Attitudes, Norms, Abilities, and Self-regulation model. At the implementer level, facilitators included building rapport and trust between implementers and participating households. Barriers included the remoteness of households, coordinating with community plumbers for arsenic filter installation, and difficulty securing a local supplier for replacement filter cartridges. At the recipient level, facilitators included knowledge of the arsenic health risks, perceived effectiveness of the filter, and visual cues to promote habit formation. Barriers included attitudes towards water taste and temperature and inability to procure or install replacement filter cartridges. This study offers insights into the successes and challenges of implementing an arsenic mitigation program tailored to American Indian households, which can inform future programs in partnership with these and potentially similar affected communities. Our study suggests that building credibility and trust between implementers and participants is important for the success of arsenic mitigation programs.