Introduction and aim Both human and equine athletes have a propensity for atrial fibrillation (AF) even in the absence of gross structural abnormalities of the heart. Risk of AF in both species is increased by extreme training. This condition often manifests as paroxysmal AF (PAF) in which ECG detection of the infrequent self-terminating fibrillation episodes is hampered by long periods of normal sinus rhythm between them. We hypothesised that the proarrhythmic background present in paroxysmal AF might be detectable by complexity analysis of short segments of normal sinus rhythm ECG. Methods Non-invasive ECG recordings were collected during routine clinical work while horses were exercised as part of their established performance assessment programmes. All subjects were Thoroughbred horses of racing age and undergoing actual race training (control group: 83 healthy horses; PAF group: 10 horses diagnosed with PAF from previous ECGs). Horses were atraumatically fitted with telemetric ECG recorders (Televet 100). Artefact-free 60-sec strips of lead II ECG were excised from telemetric ECGs and converted to binary strings using threshold crossing (TC), beat detection (BD) and a novel feature detection (FD) coarse-graining algorithms. To limit the errors caused by complexity variability at higher heart rates, strips were analysed in a 25-60 bpm range. Since a number of subjects did not provide any 60-second artefact-free normal sinus rhythm ECGs in this range, some control subjects were excluded giving a final data set of 52 subjects in the control group and 10 in the PAF group. Lempel-Ziv ’76 (LZ76) and Lempel-Ziv ‘78 (LZ78) complexity of the resulting binary strings was calculated. An unpaired two-sided t-test and ANOVA test with Tukey correction were used for group comparisons. Receiver operating curve analysis was used to assess the performance of diagnostic tests, with area under curve (AUC) as the metric. Results LZ76 (but not LZ78) complexity in combination with the FD coarse-graining algorithm is sensitive to the presence of PAF, although it did not attain a diagnostic level of accuracy (AUC = 0.79). Therefore, we introduced a heart-rate-corrected complexity metric DLZ76 which greatly improved sensitivity and specificity (fig. 1a), with AUC of 0.956 (Fig. 1b). The average DLZ76 for the controls group was 0.0118 ± 0.0095 bit/sample and for the PAF group it was −0.00954 ± 0.0103 (p < 0.001). Conclusions Our results suggest that pro-arrhythmic background present between AF episodes in PAF might be detected using the appropriately chosen ECG complexity evaluation methods. This might be developed into a fully automated method to detect PAF risk in horses by analysis of normal sinus rhythm ECG.