The natural environment is an important element in destination choice. Regional environmental change and extreme environmental events including outbreaks of species perceived as disturbing to tourists or diminishing perceived environmental quality should consequently affect tourism. However, few studies appear to have investigated these interrelationships in particular with a view to climate change, which in the future is likely to fundamentally affect landscapes, ecosystems and individual species. Coastal landscapes and marine environments are of particular importance in this context, as nature-based tourism and sun, sand and sea tourism constitute two of the most important sub-sectors of global tourism. Focusing on algal blooms occurring in the Baltic Sea in the period 2002–2006, this article investigates tourist reactions to these events in southern Sweden. Results from an online survey with 3,217 respondents indicate that perceptions of algal blooms vary widely, ranging from disinterest to annoyance and avoidance. Results also indicate that a significant share of respondents have shortened or cancelled their holidays in the regions affected because of algal blooms. Insights derived from responses are also discussed in the context of media reports on algal blooms.