Chronic kidney disease (CKD) is a potential independent risk factor for atrial fibrillation (AF). It remains unclear whether anemia is synergistically associated with increased risk of AF onset in subjects with CKD. We evaluated the association of kidney function, hemoglobin (Hb), and their combination with new-onset AF in a population-based cohort study. We conducted a 15-year prospective cohort study of 132,250 Japanese subjects aged 40 to 79 years who participated in annual health checkups from 1993. Kaplan-Meier survival analysis was used to compare freedom from new-onset AF between groups classified by estimated glomerular filtration rate grade, Hb grade, and their combination. Cox proportional hazard model analysis was used to estimate hazard ratios (HRs) for new-onset AF. During a 13.8-year mean follow-up period, 1,232 (0.93%) subjects with new-onset AF were identified. Lower estimated glomerular filtration rate and lower Hb grades were significantly associated with a higher incidence of new-onset AF. Multivariate HRs and 95% confidence intervals (CIs) of new-onset AF were 1.38 (1.21 to 1.56) for mild CKD group, 2.56 (2.09 to 3.13) for CKD group, and 1.50 (1.24 to 1.83) for anemia group. Borderline Hb level was not significantly associated with increased risk for new-onset AF (HR 1.07, CI 0.91 to 1.25, p = 0.4284). In the model with interaction term between CKD and anemia, the risk was significantly higher (p = 0.0343 for the interaction) than that predicted by each factor independently. In conclusion, decreased kidney function and lower Hb level are associated with increased risk for new-onset AF, especially when both are present.