Background: Recurrent paroxysmal atrial fibrillation (AF) after catheter ablation is presumably caused by failure to achieve durable pulmonary vein isolation (PVI). The primary methods of PVI are radiofrequency catheter ablation (RF) and cryoballoon catheter ablation (CRYO), but these methods have not been directly compared with respect to PVI durability and the effect thereof on AF burden (% of time in AF). Methods: Accordingly, we performed a randomized trial including 98 patients (68% male, 61 [55-67] years) with paroxysmal AF assigned 1:1 to PVI by contact-force sensing, irrigated radiofrequency catheter, or second-generation cryoballoon catheter. Implantable cardiac monitors were inserted ≥1 month before PVI for assessment of AF burden and recurrence, and all patients, irrespective of AF recurrence, underwent a second procedure 4 to 6 months after PVI to determine PVI durability. Results: In the second procedure, 152 out of 199 (76%) pulmonary veins (PVs) were found durably isolated after RF and 161 out of 200 (81%) after CRYO (P=0.32), corresponding to durable isolation of all veins in 47% of patients in both groups (P=1.0). Median AF burden before PVI was 5.4% (interquartile range, 0.5%-13.0%) versus 4.0% (0.6%-18.1%), RF versus CRYO (P=0.71), and reduced to 0.0% (0.0%-0.1%) and 0.0% (0.0%-0.5%), respectively (P=0.58) - a reduction of 99.9% (92.9%-100.0%) and 99.3% (85.9%-100.0%; P=0.36). AF burden after PVI significantly correlated to the number of durably isolated PVs (P<0.01), but 9 out of 45 (20%) patients with durable isolation of all veins had recurrence of AF within 4 to 6 months after PVI (excluding a 3-month blanking period). Conclusions: PVI by RF and CRYO produce similar moderate to high PVI durability. Both treatments lead to marked reductions in AF burden, which is related to the number of durably isolated PVs. However, for one-fifth of paroxysmal AF patients, complete and durable PVI was not sufficient to prevent even short-term AF recurrence. Registration: URL: https://www.clinicaltrials.gov; Unique identifier: NCT03805555.