Background Electronic medical records are increasingly used to identify disease cohorts; however, computable phenotypes using electronic medical record data are often unable to distinguish between prevalent and incident cases. Methods and Results We identified all Olmsted County, Minnesota residents aged ≥18 with a first-ever diagnostic code for atrial fibrillation or atrial flutter from 2000 to 2014 (N=6177), and a random sample with an code from 2016 to 2018 (N=200). Trained nurse abstractors reviewed all medical records to validate the events and ascertain the date of onset (incidence date). Various algorithms based on number and types of codes (inpatient/outpatient), medications, and procedures were evaluated. Positive predictive value (PPV) and sensitivity of the algorithms were calculated. The lowest PPV was observed for 1 code (64.4%), and the highest PPV was observed for 2 codes (any type) >7 days apart but within 1 year (71.6%). Requiring either 1 inpatient or 2 outpatient codes separated by >7 days but within 1 year had the best balance between PPV (69.9%) and sensitivity (95.5%). PPVs were slightly higher using codes. Requiring an anticoagulant or antiarrhythmic prescription or electrical cardioversion in addition to diagnostic code(s) modestly improved the PPVs at the expense of large reductions in sensitivity. Conclusions We developed simple, exportable, computable phenotypes for atrial fibrillation using structured electronic medical record data. However, use of diagnostic codes to identify incident atrial fibrillation is prone to some misclassification. Further study is warranted to determine whether more complex phenotypes, including unstructured data sources or using machine learning techniques, may improve the accuracy of identifying incident atrial fibrillation.