Many complex diseases are expressed with high incidence only in certain populations. Genealogy studies determine that these diseases are inherited with a high probability. However, genetic studies have been unable to identify the genomic signatures responsible for such heritability, as identifying the genetic variants that make a population prone to a given disease is not enough to explain its high occurrence within the population. This gap is known as the missing heritability problem. We know that the microbiota plays a very important role in determining many important phenotypic characteristics of its host, in particular the complex diseases for which the missing heritability occurs. Therefore, when computing the heritability of a phenotype, it is important to consider not only the genetic variation in the host but also in its microbiota. Here we test this hypothesis by studying an evolutionary model based on gene regulatory networks. Our results show that the holobiont (the host plus its microbiota) is capable of generating a much larger variability than the host alone, greatly reducing the missing heritability of the phenotype. This result strongly suggests that a considerably large part of the missing heritability can be attributed to the microbiome.