Microbial eukaryotes are diverse, ubiquitous, and play important functional roles in environmental and host-associated microbial communities. However, microbial eukaryotes are far less studied than their bacterial counterparts, due in part to methodological challenges. Several methods are available to identify taxa directly from bulk-DNA sequencing (metagenomics) data, but their species-level identification tends to be highly inaccurate or relies heavily on reference databases of complete genomes, which are particularly scarce for microbial eukaryotes. We used a novel concept in read mapping to develop CCMetagen – a metagenome classifier that is highly accurate and fast enough to use the entire NCBI nucleotide collection as reference, facilitating the inclusion of microbial eukaryotes in metagenomic studies. High accuracy is achieved by assessing all read-mapping possibilities, rather than attempting to classify individual reads. Using simulated fungal and bacterial metagenomes, we found that species-level identifications obtained with CCMetagen are between 3x and 1580x more precise than other commonly used metagenome classifiers. We applied CCMetagen to characterise the gut microbiome of wild Australian birds. Besides bacteria, we found an abundant and diverse community of microbial eukaryotes, including opportunistic fungal pathogens that would be difficult to detect with conventional tools. Our work paves the way to investigate the distribution and roles of the eukaryotic members of microbiomes.