Interactive drama concerns itself with building dramatically interesting virtual worlds inhabited by computer-controlled characters, within which the user (hereafter referred to as the player) experiences a story from a first person perspective (Bates 1992). Over the past decade there has been a fair amount of research into believable agents, that is, autonomous characters exhibiting rich personalities, emotions, and social interactions (Mateas 1997; Bates, Loyall and Reilly 1992; Blumberg 1996; Hayes-Roth, van Gent and Huber 1997; Lester and Stone 1997; Stern, Frank, and Resner 1998). There has been comparatively little work, however, exploring how the local, reactive behavior of believable agents can be integrated with the more global, deliberative nature of a story plot, so as to build interactive, dramatic worlds (Weyrauch 1997; Blumberg and Galyean 1995). The authors are currently engaged in a two to three year collaboration to build an interactive story world integrating believable agents and interactive plot. This paper provides a brief description of the project goals and design requirements, discusses the problem of autonomy in the context of story-based believable agents, and finally describes an architecture that uses the dramatic beat as a structural principle to integrate plot and character.