In a Stackelberg game, the leader can form incentives and raise threats upon followers to improve his own performance. The issue of credibility concerns whether the followers believe or not in the incentives and threats declared by the leader. In this paper, credibility is studied for two-person, single-stage games. A strategy is said to be fully credible if it satisfies the Principles of Optimality under the Stackelberg setting. The conditions for the existence of a fully credible Stackelberg strategy are explicitly stated and proved. It is shown that these conditions are fairly stringent, and are satisfied only by a very restricted class of games. When a fully credible strategy does not exist, several possible solutions are then discussed.