A multitude of challenges comes into play when attempting to design (and evaluate) an interactive digital storytelling experience for use by visitors in a museum. This paper reports on the evaluation of the prototype mobile-based storytelling “guides” designed, developed and deployed as part of a research project at the Acropolis Museum in Athens, Greece. Experiences designed for different visitor profiles were evaluated several times throughout the iterative design process, in a number of on-site studies, and with more than 180 museum visitors of all ages (with this paper reporting on two studies conducted with a total of 53 users visiting individually or in pairs). The evaluation methods included ethnography (i.e., observation of visitors in the Museum’s galleries), pre- and post-experience in-depth interviews and questionnaires to measure the Users’ Experience (UX), as well as data logging. The analysis of the data focused on themes representing components of the experiences, such as interactive story plot and narration, staging and way-finding in the physical space, personalization and social interaction. Our findings confirmed that understanding UX and what makes it effective or not in the rich context of a cultural setting is a complex endeavor. The paper discusses our findings and proposes relevant recommendations for the design of digital experiences for cultural, educational, and recreational purposes.