Previous research in economics shows that compensation based on the pay-for-performance principle is effective in inducing higher levels of effort and productivity. On the other hand, research in psychology argues that performance-based financial incentives inhibit creativity and innovation. How should managerial compensation be structured if the goal is to induce managers to pursue more innovative business strategies? In a controlled laboratory setting, we provide evidence that the combination of tolerance for early failure and reward for long-term success is effective in motivating innovation. Subjects under such an incentive scheme explore more and are more likely to discover a novel business strategy than subjects under fixed-wage and standard pay-for-performance incentive schemes. We also find evidence that the threat of termination can undermine incentives for innovation, while golden parachutes can alleviate these innovation-reducing effects.