Schema-based story understanding allows systems to process routine stories efficiently. However, a system that blindly applies active schemas may fail to recognize and understand novel events. To deal effectively with novelty, a story understander needs to be able to recognize when new information conflicts with its model of a situation. Thus it needs to be able to do anomaly detection. Anomsdy detection is the process that identifies when new information is inconsistent with current beliefs and expectations. Checking for aJl possible inconsistencies would be an explosive inference problem: it would require comparing all the ramifications of a new faw;t to all the ramifications of the facts in memory. W e argue that this inference problem can be controlled by selective consistency checking: An initial set of inexpensive tests can be applied to detect potential problems, and more thorough tests used only when a likely problem is found. W e describe a set of stereotype-based basic believability checks, designed to identify potential problems with minimal inference, and fine-grained tests that can be used to diagnose the problems that basic believability checks detect. These tests are implemented in the story understanding program ACCEPTER.