Microbiome research is a quickly developing field in biomedical research, and we have witnessed its potential in understanding the physiology, metabolism and immunology, its critical role in understanding the health and disease of the host, and its vast capacity in disease prediction, intervention and treatment. However, many of the fundamental questions still need to be addressed, including the shaping forces of microbial diversity between individuals and across time. Microbiome research falls into the classical nature vs. nurture scenario, such that host genetics shape part of the microbiome, while environmental influences change the original course of microbiome development. In this review, we focus on the nature, i.e., the genetic part of the equation, and summarize the recent efforts in understanding which parts of the genome, especially the human and mouse genome, play important roles in determining the composition and functions of microbial communities, primarily in the gut but also on the skin. We aim to present an overview of different approaches in studying the intricate relationships between host genetic variations and microbes, its underlying philosophy and methodology, and we aim to highlight a few key discoveries along this exploration, as well as current pitfalls. More evidence and results will surely appear in upcoming studies, and the accumulating knowledge will lead to a deeper understanding of what we could finally term a “hologenome”, that is, the organized, closely interacting genome of the host and the microbiome.