Equine athletes have a pattern of exercise which is analogous to human athletes and the cardiovascular risks in both species are similar. Both human and equine athletes have a propensity for atrial fibrillation (AF) which is hard to detect by ECG analysis when in paroxysmal form. We hypothesised that the proarrhythmic background present between fibrillation episodes in paroxysmal AF (PAF) might be detectable by complexity and restitution analysis of apparently normal sinus-rhythm ECGs. In this study ECG recordings were obtained during routine clinical work. Data was collected from 83 healthy horses and from 10 horses with a diagnosis of PAF. Artefact-free 60-second strips of lead II normal sinus-rhythm ECGs were excised from long ECG recordings. For the each subject, two strips of lowest heart rate (<=60 bpm) were analysed and subjects not providing sufficient data were excluded from the further study. The final control cohort therefore contained 44 control horses and PAF cohort consisted of 10 horses. We used the novel “feature detection” coarse-graining algorithm to convert the ECG recordings to binary strings. Complexity of these strings was then evaluated using Lempel-Ziv‘76 and Titchener complexity estimators. It was found that presence of paroxysmal AF is associated with decreased average complexity of ECG. For Lempel-Ziv ’76, the average complexity was decreased from .127 ± .019 to 0.099 ± .006 bit/sample, and for Titchener complexity from 0.084 ± 0.014 to 0.064 ± 0.005 bit/sample (p<0.001 in both cases). The receiver operating curve analysis produced the area under curve values above 0.94 for both complexity estimators, with estimated sensitivity and specificity of at least 0.9. This suggests that complexity analysis allows identification of horses with PAF from sinus-rhythm ECGs with high accuracy and might form the basis of a rapid and inexpensive automated method to screen horses for paroxysmal atrial fibrillation.