Seaweeds are colonized by a microbial community which can be directly linked to their performance. This community is shaped by an interplay of stochastic and deterministic processes, including mechanisms which the holobiont host deploys to manipulate its associated microbiota. The Anna Karenina Principle predicts that when a holobiont is exposed to suboptimal or stressful conditions, these host mechanisms may be compromised. This leads to a relative increase of stochastic processes that may potentially result in the succession of a microbial community harmful to the host. Based on this principle, we used the variability in microbial communities (i.e., beta diversity) as a proxy for stability within the invasive holobiont Gracilaria vermiculophylla during a simulated invasion in a common garden experiment. At elevated temperature (22 °C), host performance declined and disease incidence and beta diversity increased. At optimal temperature (15 °C), beta diversity did not differ between native and non-native populations. However, under thermally stressful conditions beta diversity increased more in epibiota from native populations. This suggests that epibiota associated with holobionts from non-native populations are under thermal stress more stable than holobionts from native populations. This pattern reflects an increase of deterministic processes acting on epibiota associated with non-native hosts, which in the setting of a common garden can be assumed to originate from the host itself. Therefore, these experimental data suggest that the invasion process may have selected for hosts better able to maintain stable microbiota during stress. Future studies are needed to identify the underlying host mechanisms.