Several studies have shown associations between groups of intestinal bacterial or specific ratios between bacterial groups and various disease traits. Meanwhile, little is known about interactions and associations between eukaryotic and prokaryotic microorganisms in the human gut. In this work, we set out to investigate potential associations between common single-celled parasites such as Blastocystis spp. and Dientamoeba fragilis and intestinal bacteria. Stool DNA from patients with intestinal symptoms were selected based on being Blastocystis spp.-positive (B+)/negative (B-) and D. fragilis-positive (D+)/negative (D-), and split into four groups of 21 samples (B+ D+, B+ D-, B- D+, and B- D-). Quantitative PCR targeting the six bacterial taxa Bacteroides, Prevotella, the butyrate-producing clostridial clusters IV and XIVa, the mucin-degrading Akkermansia muciniphila, and the indigenous group of Bifidobacterium was subsequently performed, and the relative abundance of these bacteria across the four groups was compared. The relative abundance of Bacteroides in B- D- samples was significantly higher compared with B+ D- and B+ D+ samples (P < 0.05 and P < 0.01, respectively), and this association was even more significant when comparing all parasite-positive samples with parasite-negative samples (P < 0.001). Additionally, our data revealed that a low abundance of Prevotella and a higher abundance of Clostridial cluster XIVa was associated with parasite-negative samples (P < 0.05 and P < 0.01, respectively). Our data support the theory that Blastocystis alone or combined with D. fragilis is associated with gut microbiota characterized by low relative abundances of Bacteroides and Clostridial cluster XIVa and high levels of Prevotella.