In the Archipelago Sea as in most other parts of the Baltic Sea, the bladder wrack (Fucus vesiculosus) is a foundation species of the littoral communities of the rocky shores. It sustains a community of epiphytic algae, herbivorous crustaceans and molluscs and various fish. Recently we have noticed a steep decline in the occurrence of the herbivorous crustaceans and molluscs in many sites in the Archipelago Sea. We hypothesise that a key factor contributing to this decline is the recent introduction of the Harris mud crab (Rhithropanopeus harrisii), which was first sighted in 2009 in this region. Importantly, because there are no native crabs in the northern parts of the Baltic Sea, the mud crab is a completely novel kind of predator in the ecosystem and the herbivorous crustaceans and molluscs may be particularly susceptible to it. Here, we document a dramatic decline of the typical herbivores occurring on the bladder wrack, possibly indicating an ongoing regime shift, by comparing our recent samples from across the Archipelago Sea with data collected a decade before the sighting of the mud crab. Moreover, we demonstrate a spatio-temporal association between the decline, particularly of the key herbivore species, the isopod Idotea balthica, and the establishment of the mud crab. We also present experimental evidence for a strong predator-prey -link between the mud crab and the isopod I. balthica. Finally, we discuss the possible consequences of the community change and scrutinise alternative explanations for our observations.