A long-standing goal of computer-based entertainment is the creation of a story where a user is in control of portions of the storyline. These non-linear stories give a user an opportunity to adapt the story to his or her interests, schedule and needs. The Internet has made non-linear video a reality. Different approaches have been taken to create and play non-linear video stories. They suffer from lack of simplicity, smoothness, and television-like experience in story creation and presentation. Flexible Storylines provide a way to easily create and present non-linear video stories. The creation of these stories is done using a time-line based editor that mimics the way video stories are composed by film makers. The viewing experience of flexible stories is very similar to viewing a normal video with an introduction of the choice to see more or less of the current topic. This provides a highly variable experience with a simple, smooth and non-intrusive form of user interaction. We also provide a mechanism that lets a story flow smoothly despite the introduction of user interaction.