Background: Although the importance of evaluating implementation fidelity is acknowledged, little is known about heterogeneity in fidelity over time. This study aims to generate insight into the heterogeneity in implementation fidelity trajectories of a health promotion program in multidisciplinary settings and the relationship with changes in patients' health behavior. Methods: This study used longitudinal data from the nationwide implementation of an evidence-informed physical activity promotion program in Dutch rehabilitation care. Fidelity scores were calculated based on annual surveys filled in by involved professionals (n = ± 70). Higher fidelity scores indicate a more complete implementation of the program's core components. A hierarchical cluster analysis was conducted on the implementation fidelity scores of 17 organizations at three different time points. Quantitative and qualitative data were used to explore organizational and professional differences between identified trajectories. Regression analyses were conducted to determine differences in patient outcomes. Results: Three trajectories were identified as the following: 'stable high fidelity' (n = 9), 'moderate and improving fidelity' (n = 6), and 'unstable fidelity' (n = 2). The stable high fidelity organizations were generally smaller, started earlier, and implemented the program in a more structured way compared to moderate and improving fidelity organizations. At the implementation period's start and end, support from physicians and physiotherapists, professionals' appreciation, and program compatibility were rated more positively by professionals working in stable high fidelity organizations as compared to the moderate and improving fidelity organizations (p < .05). Qualitative data showed that the stable high fidelity organizations had often an explicit vision and strategy about the implementation of the program. Intriguingly, the trajectories were not associated with patients' self-reported physical activity outcomes (adjusted model β = - 651.6, t(613) = - 1032, p = .303). Conclusions: Differences in organizational-level implementation fidelity trajectories did not result in outcome differences at patient-level. This suggests that an effective implementation fidelity trajectory is contingent on the local organization's conditions. More specifically, achieving stable high implementation fidelity required the management of tensions: realizing a localized change vision, while safeguarding the program's standardized core components and engaging the scarce physicians throughout the process. When scaling up evidence-informed health promotion programs, we propose to tailor the management of implementation tensions to local organizations' starting position, size, and circumstances. Trial registration: The Netherlands National Trial Register NTR3961. Registered 18 April 2013.