This study proposes a novel noninvasive ECG-based approach to accurately quantify differences in the atrial activity (AA) signals of atrial fibrillation (AF) patients characterized by very similar global AF organization. High-density body surface potential maps were recorded in 63 patients in persistent AF prior to electrical cardioversion (32 recurrences occurred after 4–6 weeks). AF substrate complexity was quantified as the degree of overall temporal organization of the AA pattern, determined from multi-variable unthresholded recurrence plots (RP). Results showed that non-recurrent patients were characterized by temporally more stable propagation patterns than recurrent patients, suggesting a lower complexity of the AF substrate in the former This was used to discriminate between recurrent and non-recurrent AF patients following electrical cardioversion with an accuracy of 72%. Noninvasive assessment of AF substrate complexity in patients characterized by very similar levels of AF progression was improved by applying RP-based analysis on extracted AA signals. The proposed approach may help improving AF treatment selection and success.