Virtual cultural heritage applications, particularly virtual museums, nowadays include various forms of storytelling. Every object, site or artifact is better perceived and understood through the adjoining story. Interactive applications naturally request the storytelling to become interactive as well. This paper describes the concepts of interactive digital storytelling in our virtual museums and cultural heritage presentations and discusses their advantages and drawbacks recognized through user evaluation. We used digital stories not only to introduce visitors with the context and information on the objects, but also to enhance their navigation through virtual environments with purpose of learning and perceiving maximum amount of offered information.