Trained cardiologists detect atrial fibrillation by visual interpretation of certain segments of electrocardiogram (EKG) lines known as the QRS complex. Similarly, available EKG-software also evaluates anomalies in the signals from the EKG-leads that produce the traces/lines in order to flag for atrial fibrillation. We and others have previously shown that machine learning methods successfully identify patients with paroxysmal atrial fibrillation (PAF) based on their EKG during normal sinus rhythm. In this work, we go beyond the earlier black-box approaches and identify specific patterns in the QRS complex of a normal sinus rhythm that are associated with atrial fibrillation. We implemented frequent pattern mining on discretized waveform raw EKG data to determine patterns that are specific to patients with PAF based on 1-minute Lead 1 EKG recordings sampled at 128 Hz from 25 patients with PAF and 50 healthy subjects from a Physionet data repository. We discretized the down-sampled (16 Hz) EKG traces with seven symbols corresponding to various degrees of local variability within the traces and selected from the existing unique 1,306 4-symbol patterns the 850 patterns occurring at least 5 times (to mitigate sparsity related problems). The resulting 75x850 pattern frequency matrix represented the frequency of each pattern within each of the 75 patients and PAF subjects were distinguished based on a binary Least Absolute Shrinkage and Selection Operator regression with 5-fold cross validation that selected 50 of the patterns (AUC = 0.95; 95% C.I. 0.88-1.00; 94% specificity, 88% sensitivity). These 50 patterns are candidates to elicit the “fingerprint” of PAF within normal sinus rhythm: e.g., one of the selected patterns in Figure 1 was observed in 76% of PAF patients while it was present only in 30% of healthy patients. Our study is a proof of concept that machine learning and artificial intelligence techniques are not restricted to black-box approaches and can be used to derive interpretable insights that could lead to novel biomarkers associated with certain health conditions.