Leader behavioral integrity (BI) is central to perceived credibility and thus to leaders’ effectiveness at fostering ethical and other climates. Our research broadens the theoretical foundation for BI research by integrating the cognitive–attributional role of trust in the formation and maintenance of leader BI perceptions. Guided by recent research on trust primacy and prior theories of fairness used to examine ethical behavior, we examine how perceptions of leader BI can be either diminished or maintained through trust velocity following a psychological contract breach. Using a field and an experimental study, we explore the manner in which followers perceive leader’s actions when conflicting interests lead to unfulfilled promises. We found that trust velocity mediates the relationship between a psychological contract breach and leader BI (study 1), and that informational justice moderates this relationship (study 2), suggesting that leaders can attenuate the impact of broken promises on ascribed BI. Our findings offer a pathway for leaders operating in dynamic contexts to preserve BI and also help address concerns that have been raised about the behavioral integrity construct regarding its conceptual overlap with related constructs such as trust, psychological contracts, and informational justice.