Worldwide, marine rocky shores are being modified by alien species, but their successive impacts are rarely recorded. We documented sequential invasions of Marcus Island on the west coast of South Africa by comparing communities from 1980 (pre-invasion), 2001 (after invasion by the mussel Mytilus galloprovincialis) and 2012 (following invasions by another mussel, Semimytilus algosus, and the barnacle Balanus glandula). Their influence on habitat complexity was measured with a novel technique enabling retrospective calculation of historical complexity. In 1980, habitat complexity, invertebrate abundance and species richness decreased from the low-shore to the high-shore, but homogenised in 2001 after Mytilus galloprovincialis elevated habitat complexity across most of the shore. In 2012, these variables returned to pre-invasion patterns, after Mytilus galloprovincialis declined in the high-shore and was replaced there by Balanus glandula. With the first mussel invasion, several indigenous species extended up the intertidal, but retreated once Mytilus galloprovincialis receded. Community composition differed significantly among nearly all years and zones, irrespective of whether the alien species were included in the analyses or not. Some once-dominant native species were negatively affected by the invasions: one indigenous mussel, Choromytilus meridionalis, disappeared by 2012, and another, Aulacomya atra, declined. The abundance of recruits of the limpet Scutellastra granularis rose and fell with the arrival and recession of Mytilus galloprovincialis, but adults were adversely affected. Changes to habitat complexity induced by sequential invasions supported hypothesised changes in invertebrate abundance and species richness, but could not alone predict changes in community composition, which were also influenced by zonation.