The pursuit of highly sensitive and specific cancer diagnostics based on cell-free (cf) nucleic acids isolated from minimally invasive liquid biopsies has been an area of intense research and commercial effort for at least two decades. Most of these tests detect cancer-specific mutations or epigenetic modifications on circulating DNA derived from tumor cells (ctDNA). Although recent FDA approvals of both single and multi-analyte liquid biopsy companion diagnostic assays are proof of the tremendous progress made in this domain, using ctDNA for the diagnosis of early-stage (stage I/II) cancers remains challenging due to several factors, such as low mutational allele frequency in circulation, overlapping profiles in genomic alterations among diverse cancers, and clonal hematopoiesis. This review discusses these analytical challenges, interim solutions, and the opportunity to complement ctDNA diagnostics with microbiome-aware analyses that may mitigate several existing ctDNA assay limitations.