Current models of animal evolution focus on selection of individuals, ignoring the much faster selection of symbiotic bacteria. Here we take host-symbiont interactions into account by introducing a Population Genetics-like model of holobionts exposed to toxic stress. The stress can be alleviated by selection of resistant individuals (host and bacteria) and by secretion of a detoxification agent (“detox”). By defining a new measure, termed the ‘Lamarckian’, we show that selection of resistant bacteria over one generation of hosts leads to stress-dependent increase in the tolerance of the hosts' offspring. This benefit is mediated by co-alleviation of toxic and physiologic stress. Prolonged exposure leads to further adaptation by ‘group selection’ of bacterial communities with higher detox per bacterium. These findings show that Lamarckian adaptation can arise via interactions between two levels of Darwinian selection within a holobiont system. The conclusions and modelling framework are applicable to diverse types of holobiont systems.