Host-associated microbiota form complex microbial communities that are increasingly associated with host behavior and disease. While these microbes include bacterial, archaeal, viral, and eukaryotic constituents, most studies have focused on bacteria due to their dominance in the human host and available tools for investigation. Accumulating evidence suggests microbial eukaryotes in the microbiome play pivotal roles in host health, but our understandings of these interactions are limited to a few readily identifiable taxa because of technical limitations in unbiased eukaryote exploration. Here, we combined cell sorting, optimized eukaryotic cell lysis, and shotgun sequencing to accelerate metagenomic discovery and analysis of host-associated microbial eukaryotes. Using synthetic communities with a 1% microbial eukaryote representation, the eukaryote-optimized cell lysis and DNA recovery method alone yielded a 38-fold increase in eukaryotic DNA. Automated sorting of eukaryotic cells from stool samples of healthy adults increased the number of microbial eukaryote reads in metagenomic pools by up to 28-fold compared to commercial kits. Read frequencies for identified fungi increased by 10,000× on average compared to the Human Microbiome Project and allowed for the identification of novel taxa, assembly of contigs from previously unknown microbial eukaryotes, and gene prediction from recovered genomic segments. These advances pave the way for the unbiased inclusion of microbial eukaryotes in deciphering determinants of health and disease in the host-associated microbiome.IMPORTANCEMicrobial eukaryotes are common constituents of the human gut where they can contribute to local ecology and host health, but they are often overlooked in microbiome studies. The lack of attention is due to current technical limitations that are heavily biased or poorly recovered DNA from microbial eukaryotes. We developed a method to increase the representation of these eukaryotes in metagenomic sequencing of microbiome samples that allows to improve their detection compared to prior methods and allows for the identification of new species. Application of the technique to gut microbiome samples improved detection of fungi, protists, and helminths. New eukaryotic taxa and their encoded genes could be identified by sequencing a small number of samples. This approach can improve the inclusion of eukaryotes into microbiome research.