Situational complexity is the distinction between simple, technically complicated, socially complicated, and complex situations. Programs that operate in simple situations are usually able to follow a prescribed course of action, or recipe, while programs operating in more complicated or complex situations must be flexible and responsive. In this article, the authors present findings from an exploratory, multiple-case study of the credibility of evidence in four distinct program situations ranging from simple to complex. Key informant interviews were conducted with 16 key informants, both internal and external to Extension. The findings were generally that the more complex the situation, the more likely that flexible or mixed-methods approaches were employed to strengthen program credibility. Across all the cases, the relationships that Extension educators have built with stakeholders played a pivotal role in building credibility of evidence. We conclude that sometimes situational complexity matters, sometimes methods matter, sometimes reporting style matters, but what always matters is the trusting relationship between the delivery organization and the stakeholder.