Kidney transplantation (KT) is the best treatment for end-stage kidney disease, with graft survival critically affected by the recipient's immune response. The role of the gut microbiome in modulating this immune response remains underexplored. Our study investigates how microbiome alterations might be associated with allograft rejection by analyzing the gut microbiome using 16S rRNA gene amplicon sequencing of a multicenter prospective study involving 562 samples from 245 individuals of whom 217 received KT. Overall, gut microbiome composition showed gradual recovery post-KT, mirroring chronic kidney disease (CKD)-to-health transition as indicated by an increase in Shannon diversity. Prior to graft rejection, we observed a decrease in microbial diversity and short-chain fatty acid-producing taxa. Functional analysis highlighted a decreased potential for short-chain fatty acid production in patients preceding the rejection event, validated by quantitative PCR for the production potential of propionate and butyrate. Postrejection analysis revealed normalization of these microbiome features. Comparison to published microbiome signatures from CKD patients demonstrated a partial overlap of the microbiome alterations preceding graft rejection with the alterations typically found in CKD. Our findings suggest that alterations in gut microbiome composition and function may precede and influence KT rejection, suggesting potential implications as biomarkers or for early therapeutic microbiome-targeting interventions.