The human microbiome - the vast amount of microbes that colonize our body - play an important role in maintaining our health. Changes in microbiome composition have been linked to multiple diseases including cancer. Although mechanisms and causalities of these associations still have to be uncovered, microbiome alterations across various stages of disease can be utilized for novel diagnostic and prognostic tests. Research on biomarkers extracted from the gut microbiome has in particular focused on colorectal cancer, where clinical use is already on the horizon. For example, multiple microbial taxonomic markers such as Fusobacterium nucleatum and other oral pathogens have been identified in human feces with potential for non-invasive diagnostics and prognostics. The article summarizes the recent developments, but also limitations and challenges for the development of microbiome-based biomarkers for cancer early detection.