Growing evidence implicates the gut microbiome in cognition. Blastocystis is a common gut single-cell eukaryote parasite frequently detected in humans but its potential involvement in human pathophysiology has been poorly characterized. Here we describe how the presence of Blastocystis in the gut microbiome was associated with deficits in executive function and altered gut bacterial composition in a discovery (n = 114) and replication cohorts (n = 942). We also found that Blastocystis was linked to bacterial functions related to aromatic amino acids metabolism and folate-mediated pyrimidine and one-carbon metabolism. Blastocystis-associated shifts in bacterial functionality translated into the circulating metabolome. Finally, we evaluated the effects of microbiota transplantation. Donor's Blastocystis subtypes led to altered recipient's mice cognitive function and prefrontal cortex gene expression. In summary, Blastocystis warrant further consideration as a novel actor in the gut microbiome-brain axis.