Marine multicellular organisms host a diverse collection of bacteria, archaea, microbial eukaryotes, and viruses that form their microbiome. Such host-associated microbes can significantly influence the host’s physiological capacities; however, the identity and functional role(s) of key members of the microbiome (“core microbiome”) in most marine hosts coexisting in natural settings remain obscure. Also unclear is how dynamic interactions between hosts and the immense standing pool of microbial genetic variation will affect marine ecosystems’ capacity to adjust to environmental changes. Here, we argue that significantly advancing our understanding of how host-associated microbes shape marine hosts’ plastic and adaptive responses to environmental change requires (i) recognizing that individual host–microbe systems do not exist in an ecological or evolutionary vacuum and (ii) expanding the field toward long-term, multidisciplinary research on entire communities of hosts and microbes. Natural experiments, such as time-calibrated geological events associated with well-characterized environmental gradients, provide unique ecological and evolutionary contexts to address this challenge. We focus here particularly on mutualistic interactions between hosts and microbes, but note that many of the same lessons and approaches would apply to other types of interactions.