Atrial fibrillation is the most frequent arrhythmia in both equine and human athletes. Currently, this condition is diagnosed via electrocardiogram (ECG) monitoring which lacks sensitivity in about half of cases when it presents in paroxysmal form. We investigated whether the arrhythmogenic substrate present between the episodes of paroxysmal atrial fibrillation (PAF) can be detected using restitution analysis of normal sinus-rhythm ECGs. In this work, ECG recordings were obtained during routine clinical work from control and horses with PAF. The extracted QT, TQ, and RR intervals were used for ECG restitution analysis. The restitution data were trained and tested using k-nearest neighbor (k-NN) algorithm with various values of neighbors k to derive a discrimination tool. A combination of QT, RR, and TQ intervals was used to analyze the relationship between these intervals and their effects on PAF. A simple majority vote on individual record (one beat) classifications was used to determine the final classification. The k-NN classifiers using two-interval measures were able to predict the diagnosis of PAF with area under the receiving operating characteristic curve close to 0.8 (RR, TQ with k ≥ 9) and 0.9 (RR, QT with k ≥ 21 or TQ, QT with k ≥ 25). By simultaneously using all three intervals for each beat and a majority vote, mean area under the curves of 0.9 were obtained for all tested k-values (3-41). We concluded that 3D ECG restitution analysis can potentially be used as a metric of an automated method for screening of PAF.