Previous work on story planning has lacked a knowledge representation for characters that make mistakes in the execution of their actions. In particular, characters' execution mistakes that arise from errors in belief have not been modeled. In this paper, we describe a state-space planning system and its belief model, together called HeadSpace, that generates stories that track and manipulates characters' belief about the story world around them. This model is used to produce actions in stories that are attempted but that fail. We show an example story plan that contains failed-action content that cannot be generated by typical planning-based approaches to story creation.