By following up the gut microbiome, 51 human phenotypes and plasma levels of 1,183 metabolites in 338 individuals after 4 years, we characterize microbial stability and variation in relation to host physiology. Using these individual-specific and temporally stable microbial profiles, including bacterial SNPs and structural variations, we develop a microbial fingerprinting method that shows up to 85% accuracy in classifying metagenomic samples taken 4 years apart. Application of our fingerprinting method to the independent HMP cohort results in 95% accuracy for samples taken 1 year apart. We further observe temporal changes in the abundance of multiple bacterial species, metabolic pathways, and structural variation, as well as strain replacement. We report 190 longitudinal microbial associations with host phenotypes and 519 associations with plasma metabolites. These associations are enriched for cardiometabolic traits, vitamin B, and uremic toxins. Finally, mediation analysis suggests that the gut microbiome may influence cardiometabolic health through its metabolites.