Parkinson's disease (PD) exhibits systemic effects on the human metabolism, with emerging roles for the gut microbiome. Here, we integrate longitudinal metabolome data from 30 drug-naive, de novo PD patients and 30 matched controls with constraint-based modeling of gut microbial communities derived from an independent, drug-naive PD cohort, and prospective data from the general population. Our key results are (1) longitudinal trajectory of metabolites associated with the interconversion of methionine and cysteine via cystathionine differed between PD patients and controls; (2) dopaminergic medication showed strong lipidomic signatures; (3) taurine-conjugated bile acids correlated with the severity of motor symptoms, while low levels of sulfated taurolithocholate were associated with PD incidence in the general population; and (4) computational modeling predicted changes in sulfur metabolism, driven by A. muciniphila and B. wadsworthia, which is consistent with the changed metabolome. The multi-omics integration reveals PD-specific patterns in microbial-host sulfur co-metabolism that may contribute to PD severity.