Background: The clinical benefit of concomitant atrial fibrillation (AF) ablation at the time of aortic valve replacement (AVR) is uncertain. Methods and Results: A total of 124 patients with AF who underwent AVR with (n=50) or without (n=74) a concomitant maze procedure, between 2000 and 2011, were evaluated. There were no significant differences in early postoperative outcomes. During a median clinical follow-up of 18.1 months (interquartile range: 6.9–47.8 months), 19 late deaths (15.3%) and 33 valve-related complications (26.6%) occurred, but the differences between groups were not statistically significant. Major event-free survival at 5 years was 60.9±9.9% vs. 57.0±10.3% (P=0.41). After adjustment, the maze group demonstrated similar risks for major adverse cardiac events (hazard ratio, 1.18; 95% confidence interval, 0.56–2.49; P=0.67). However, the rate of sinus rhythm restoration at 4 years was significantly higher in the maze group (80.6% vs. 3.6%, P<0.001). Left atrial dimension was smaller (46.9 vs. 50.4mm, P=0.017), and the ejection fraction was higher (60.6% vs. 58.0%, P=0.059) in the maze group. The rate of postoperative anticoagulation was also lower in the maze group (53.1% vs. 89.2%, P<0.001). Conclusions: Concomitant AF ablation in patients undergoing AVR resulted in increased sinus rhythm restoration, better echocardiographic results, and decreased anticoagulation requirement, without increasing surgical morbidity or mortality.