When plants and animals appeared on Earth, the planet was already crowded with microbes.  Therefore, the evolution of multicellular organisms did not only take place in the presence of microbes but, in many cases, it was possible only with their help. Throughout evolution, microbes and multicellular organisms established long-lasting symbiotic relationships observed to this day. These symbiotic interactions are so strong that some scientists have suggested that the very concept of “individual” has to be reformulated (or extended) in order to incorporate these interdependencies in evolutionary theories. Thus, the concept of “holobiont” (the multicellular host plus its microbiota) has emerged as a unit of selection in evolution. We present an evolutionary model, based on complex network dynamics, showing that the interaction with microbes greatly improves the adaptation of the host to perform new functions. Furthermore, a great microbial diversity is required for the host to develop multiple phenotypes to perform different tasks. Disrupting these interactions often leads to non-adaptive states, reminiscent of dysbiosis, where none of the networks the holobiont consists of can perform their respective functions. By considering the holobiont as a unit of selection and focusing on the adaptation of the host to predefined but arbitrary functions, our model reproduces many patterns regarding the emergence of host-microbe symbiotic interactions and predicts the need for specialized diversity in the microbiota.