Background and Aim: Plant-based diets are associated with potential health benefits, but the contribution of gut microbiota remains to be clarified. We aimed to identify differences in key features of microbiome composition and function with relevance to metabolic health in individuals adhering to a vegan vs. omnivore diet. Methods: This cross-sectional study involved lean, healthy vegans (n = 62) and omnivore (n = 33) subjects. We assessed their glucose and lipid metabolism and employed an integrated multi-omics approach (16S rRNA sequencing, metabolomics profiling) to compare dietary intake, metabolic health, gut microbiome, and fecal, serum, and urine metabolomes. Results: The vegans had more favorable glucose and lipid homeostasis profiles than the omnivores. Long-term reported adherence to a vegan diet affected only 14.8% of all detected bacterial genera in fecal microbiome. However, significant differences in vegan and omnivore metabolomes were observed. In feces, 43.3% of all identified metabolites were significantly different between the vegans and omnivores, such as amino acid fermentation products p-cresol, scatole, indole, methional (lower in the vegans), and polysaccharide fermentation product short- and medium-chain fatty acids (SCFAs, MCFAs), and their derivatives (higher in the vegans). Vegan serum metabolome differed markedly from the omnivores (55.8% of all metabolites), especially in amino acid composition, such as low BCAAs, high SCFAs (formic-, acetic-, propionic-, butyric acids), and dimethylsulfone, the latter two being potential host microbiome co-metabolites. Using a machine-learning approach, we tested the discriminative power of each dataset. Best results were obtained for serum metabolome (accuracy rate 91.6%). Conclusion: While only small differences in the gut microbiota were found between the groups, their metabolic activity differed substantially. In particular, we observed a significantly different abundance of fermentation products associated with protein and carbohydrate intakes in the vegans. Vegans had significantly lower abundances of potentially harmful (such as p-cresol, lithocholic acid, BCAAs, aromatic compounds, etc.) and higher occurrence of potentially beneficial metabolites (SCFAs and their derivatives).