Abstract Sequencing technologies have fueled a rapid rise in descriptions of microbial communities associated with hosts, but what is often harder to ascertain is their evolutionary significance. Here we review the existing literature on the role of vertical (VT), horizontal (HT), environmental acquisition, and mixed modes (MMT) of transmission for establishing animal host-microbe associations. We then modelled 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: (i) MMT led to the highest frequencies of host-microbe associations, and some environmental acquisition or HT of microbes was required for persistent associations to form unless VT was perfect; (ii) host reproductive mode (sexual vs asexual) and host mate choice (for microbe carriers vs 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; (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.