Abstract Aims Accurate determination of intra-atrial conduction velocity (CV) is essential to identify arrhythmogenic areas. The most optimal, commonly used, estimation methodology to measure conduction heterogeneity, including finite differences (FiD), polynomial surface fitting (PSF), and a novel technique using discrete velocity vectors (DVV), has not been determined. We aim (i) to identify the most suitable methodology to unravel local areas of conduction heterogeneities using high-density CV estimation techniques, (ii) to quantify intra-atrial differences in CV, and (iii) to localize areas of CV slowing associated with paroxysmal atrial fibrillation (PAF). Methods and results Intra-operative epicardial mapping (>5000 sites, interelectrode distances 2 mm) of the right and left atrium and Bachmann’s bundle (BB) was performed during sinus rhythm (SR) in 412 patients with or without PAF. The median atrial CV estimated using the DVV, PSF, and FiD techniques was 90.0 (62.4–116.8), 92.0 (70.6–123.2), and 89.4 (62.5–126.5) cm/s, respectively. The largest difference in CV estimates was found between PSF and DVV which was caused by smaller CV magnitudes detected only by the DVV technique. Using DVV, a lower CV at BB was found in PAF patients compared with those without atrial fibrillation (AF) [79.1 (72.2–91.2) vs. 88.3 (79.3–97.2) cm/s; P < 0.001]. Conclusions Areas of local conduction heterogeneities were most accurately identified using the DVV technique, whereas PSF and FiD techniques smoothen wavefront propagation thereby masking local areas of conduction slowing. Comparing patients with and without AF, slower wavefront propagation during SR was found at BB in PAF patients, indicating structural remodelling.