Microbial eukaryotes are diverse, ubiquitous, and play important functional roles in environmental and host-associated microbial communities. However, micro-eukaryotes are far less studied than their bacterial counterparts, due in part to methodological challenges. Several methods are available to identify taxa directly from metagenome 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 17x and 1580x more precise than other commonly used metagenome classifiers. We applied CCMetagen to characterize the gut microbiome of wild birds using RNA-based metagenomic data (metatranscriptomics). Besides prokaryotes, we found an abundant and diverse community of micro-eukaryotes, with fungal taxa composing 50% of the family-level diversity of the bird microbiome. Our work opens possibilities to confidently include microbial eukaryotes in studies seeking ecological and evolutionary insights from metagenomes.