Sequencing technologies have fuelled a rapid rise in descriptions of microbial communities associated with hosts, but what is often harder to ascertain is the evolutionary significance of these symbioses. Here, we review the role of vertical (VT), horizontal (HT), environmental acquisition and mixed modes of transmission (MMT), in the establishment of animal host–microbe associations. We then model four properties of gut microbiota proposed as key to promoting animal host–microbe relationships: modes of transmission, host reproductive mode, host mate choice and host fitness. We found that: (i) MMT led to the highest frequencies of host–microbe associations, and that some environmental acquisition or HT of microbes was required for persistent associations to form unless VT was perfect; (ii) host reproductive mode (sexual versus asexual) and host mate choice (for microbe carriers versus non-carriers) had little impact on the establishment of host–microbe associations; (iii) host mate choice did not itself lead to reproductive isolation, but could reinforce it; and (iv) changes in host fitness due to host–microbe associations had a minimal impact upon the formation of co-associations. When we introduced a second population, into which host–microbe carriers could disperse but in which environmental acquisition did not occur, highly efficient VT was required for host–microbe co-associations to persist. Our study reveals that transmission mode is of key importance in establishing host–microbe associations