The role of the gut microbiome in the development of renal stone diseases has not been well characterized. This study focused on the taxonomic and functional profiles of gut microbiomes according to the prevalence and incidence of nephrolithiasis. Stool samples from 915 Korean adults were collected at baseline. Participants were followed for a median of 4.0 years. We evaluated the biodiversity of the gut microbiota and taxonomic profiles associated with nephrolithiasis status, using 16S rRNA gene sequencing. Nephrolithiasis status was categorized into three groups: control (no-stone at both baseline and follow-up visits), incidental nephrolithiasis, and prevalent nephrolithiasis. Compared to the control and incidental nephrolithiasis, the prevalent nephrolithiasis showed a reduced evenness in alpha diversity. Nephrolithiasis was associated with a reduced abundance of some key taxa involved in short-chain fatty acid production. Moreover, the abundance of Bifidobacterium, which possess oxalate-degrading ability, was higher in the control. Conversely, there was no significant difference in the bacterial composition between the incidental and prevalent nephrolithiasis. In our study with repeated nephrolithiasis measurements, prevalent renal stones were associated with an altered gut microbiota composition compared to the control. Besides the known oxalate degradation pathway, other functional pathways inferred in this study require further investigation.