Planning-based techniques are powerful tools for automated narrative generation, however, as the planning domain grows in the number of possible actions traditional planning techniques suffer from a combinatorial explosion.  In this work, we apply Monte Carlo Tree Search to goal-driven narrative generation. We demonstrate our approach to have an order of magnitude improvement in performance over traditional search techniques when planning over large story domains. Additionally, we propose a Bayesian story evaluation method to guide the planning towards believable narratives which achieve user-defined goals.  Finally, we present an interactive user interface which enables users of our framework to modify the believability of different actions, resulting in greater narrative variety.