Human language and intelligence go far beyond biological needs, allowing us to discuss abstract ideas, construct imaginary worlds, and do science and mathematics. How did such an ability arise? I propose that a major contributing factor was an arms race between truth and deception in storytelling. In honeybees, an elaborate language could evolve because reproductive conflicts of interest between individuals were reduced. For humans, however, reproductive conflicts of interest became a spur for increasing intelligence. Through the drive to negotiate social interactions, primate intelligence reached the point where knowledge could be shared through basic problem-resolution proto-stories, building on the way animals learn. As soon as honest proto-stories became possible, so did dishonest ones, ushering in an arms race between truth and deception, through which stories, language and skills in detecting lies through contradictions, were driven to ever greater heights. In telling stories to others, humans also told them to themselves, allowing them to think consciously and plan ahead. Through fictions they could share understanding by making discrepancies stronger and more engaging. Science arose when skills in detecting lies through empirical contradictions were applied to stories about how the world operates, whereas mathematics arose when skills in discerning lies through self-contradiction were applied to abstract reasoning. Both scientists and mathematicians used the storytelling structure of problem-chain-resolution to share their findings, founded on the principles of animal learning. Human intelligence thus arose through, and continues to depend upon, a balance between trust and doubt in the stories we share.