The human gut microbiome is a complex ecosystem that is involved in its host's metabolism, immunity and health. Although interindividual variations in gut microbial composition are mainly driven by environmental factors, some gut microorganisms are heritable and thus can be influenced by host genetics. In the past 5 years, 12 microbial genome-wide association studies (mbGWAS) with >1,000 participants have been published, yet only a few genetic loci have been consistently confirmed across multiple studies. Here we discuss the state of the art for mbGWAS, focusing on current challenges such as the heterogeneity of microbiome measurements and power issues, and we elaborate on potential future directions for genetic analysis of the microbiome.