Thierry Henry inspired an Arsenal comeback as the Gunners' FA Cup record continued at Elland Road.
Arsenal have not lost in this competition since the 2001 final, but they went behind to a Mark Viduka goal after Jens Lehmann's clearance hit him.
But Henry guided home a Frederik Ljungberg cross then supplied Edu with the pass for Arsenal's second.
Substitute Robert Pires ended the tie with a cool finish before setting up Kolo Toure in stoppage time.
Leeds looked more assured from the kick-off, with James Milner - in for Jermaine Pennant after Arsenal refused to let the on-loan winger play - keen to make the most of his chance on his 18th birthday.
The Gunners - who made six changes from the 1-0 win over Southampton - seemed uncomfortable on the ball and uncharacteristically gave the ball away far too easily.
8 mins: Lehmann's error gifts Viduka a goal
26 mins: Henry converts Ljungberg's cross
33 mins: Edu slots home
87 mins: Pires wraps it up
90 mins: Toure volleys in
They were made to pay when Lehmann took a heavy touch from a back pass and slammed his clearance straight at Viduka, the German stopper watching on helplessly as the ball sailed into the net.
Arsenal were at sixes and sevens and Milner and Viduka both went close to increasing Leeds' advantage.
But they had not accounted for Henry. A flowing move down the right led to a Ljungberg cross and the French striker effortlessly caressed the ball into the net on the volley.
Ten minutes later and the turnaround was complete. This time it was Henry who raced away down the left, and his sliderule pass was converted on the stretch by Edu.
Edu slides home Arsenal's second
Arsenal came out for the second half keen to end the game as a contest, and two chances in quick succession should have brought another goal.
First Kanu's goalbound drive was hacked off the line by Matthew Kilgallon, then Edu's corner was powerfully headed over by an unmarked Campbell.
But like the visitors in the first half, Leeds eventually began to enjoy greater spells in possession and they set about searching for an equaliser.
Eirik Bakke's wickedly outswinging cross was brilliantly cleared from danger by Martin Keown before Kilgallon's shot was blocked by Campbell.
Just as it looked like Leeds would level Arsenal almost broke away to score, a deflection falling kindly to Kanu, whose shot on the turn was parried away by Paul Robinson.
Henry then sent Ljungberg away with a skilful flick of his right boot, but the Swede could only slice his effort wide after racing into the penalty area.
Leeds probed as the clock ticked down, but Arsenal substitute Pires ended any hopes they had of a replay by sliding the ball past Robinson from Henry's centre.
And then in injury time Pires crossed for Toure to side-foot home - the third time in a row Arsenal have scored four past Leeds at Elland Road.
Leeds: Robinson, Richardson, Duberry, Kilgallon, Harte,
Bakke (Sakho 70), Smith, Batty, Matteo, Milner (Lennon 84),
Subs Not Used: Carson, Johnson, Olembe.
Booked: Bakke, Smith.
Arsenal: Lehmann, Lauren, Keown, Campbell, Cole,
Ljungberg (Toure 81), Vieira, Silva, Edu (Parlour 80),
Kanu (Pires 81), Henry.
Subs Not Used: Shaaban, Bentley.
Referee: R Styles (Hampshire).