Promoting First Relationship (PFR) is an evidence-based intervention designed to promote positive, supportive relationships between primary caregivers and their young children. Implementing and testing the efficacy of PFR in a remote Native community is especially challenging and requires methods and tools for ensuring implementation fidelity. Tribal members of a Native community were successfully trained and certified to deliver PFR by university-based personnel. During PFR delivery, they achieved very high scores on adherence to intervention content (M = 0.99, SD = 0.02), and their quality of delivery uniformly exceeded established criteria. High attrition occurred before PFR was delivered. However, participants who remained in the study completed all 10 sessions of PFR content. Participants' satisfaction with the program was very high (M = 3.90 [of 4 points], SD = 0.19). High implementation fidelity was attained in the face of many inherent challenges. The suite of methods and tools used for training, monitoring, and evaluating implementation fidelity in this study provides an example that may be useful in the evaluation of evidence-based programs more generally.