Although growing evidence links air pollution to stroke incidence, less is known about the effect of air pollution on atrial fibrillation (AF), an important risk factor for stroke.We assessed the associations between air pollution and incidence of AF and stroke. We also sought to characterize the shape of pollutant-disease relationships.The population-based cohort comprised 5,071,956 Ontario residents, age 35-85 y and without the diagnoses of both outcomes on 1 April 2001 and was followed up until 31 March 2015. AF and stroke cases were ascertained using health administrative databases with validated algorithms. Based on annual residential postal codes, we assigned 5-y running average concentrations of fine particulate matter ([Formula: see text]), nitrogen dioxide ([Formula: see text]), and ozone ([Formula: see text]) from satellite-derived data, a land-use regression model, and a fusion-based method, respectively, as well as redox-weighted averages of [Formula: see text] and [Formula: see text] ([Formula: see text]) for each year. Using Cox proportional hazards models, we estimated the hazard ratios (HRs) and 95% confidence intervals (95% CIs) of AF and stroke with each of these pollutants, adjusting for individual- and neighborhood-level variables. We used newly developed nonlinear risk models to characterize the shape of pollutant-disease relationships.Between 2001 and 2015, we identified 313,157 incident cases of AF and 122,545 cases of stroke. Interquartile range increments of [Formula: see text], [Formula: see text], [Formula: see text], and [Formula: see text] were associated with increases in the incidence of AF [HRs (95% CIs): 1.03 (1.01, 1.04), 1.02 (1.01, 1.03), 1.01 (1.00, 1.02), and 1.01 (1.01, 1.02), respectively] and the incidence of stroke [HRs (95% CIs): 1.05 (1.03, 1.07), 1.04 (1.01, 1.06), 1.05 (1.03, 1.06), and 1.05 (1.04, 1.06), respectively]. Associations of similar magnitude were found in various sensitivity analyses. Furthermore, we found a near-linear association for stroke with [Formula: see text], whereas [Formula: see text], [Formula: see text]-, and [Formula: see text] relationships exhibited sublinear shapes.Air pollution was associated with stroke and AF onset, even at very low concentrations. https://doi.org/10.1289/EHP4883.