The present study evaluated the associations between gallstones and renal stones using a national sample cohort of the Korean population. The Korean National Health Insurance Service-National Sample Cohort was collected from 2002 to 2013. We designed two different longitudinal follow-up studies. In study I, we extracted gallstone patients (n = 20,711) and 1:4-matched control I subjects (n = 82,844) and analyzed the occurrence of renal stones. In study II, we extracted renal stone patients (n = 23,615) and 1:4-matched control II subjects (n = 94,460) and analyzed the occurrence of gallstones. Matching was performed for age, sex, income, region of residence, and history of hypertension, diabetes mellitus, and dyslipidemia. Crude and adjusted hazard ratios (HRs) were calculated using a Cox proportional hazards model, and the 95% confidence intervals (CIs) were calculated. Subgroup analyses were performed according to age and sex. The adjusted HR of renal stones was 1.93 (95% CI = 1.75-2.14) in the gallstone group (P < 0.001). The adjusted HR of gallstones was 1.97 (95% CI = 1.81-2.15) in the renal stone group (P < 0.001). The results were consistent in all subgroup analyses. Gallstones increased the risk of renal stones, and renal stones increased the risk of gallstones.