A 19th-minute goal from in-form striker Jermaine Beckford gave the League One (third division) leaders victory as United lost at this stage of the competition for the first time since third division Bournemouth beat them in 1984.
Beckford struck his fifth goal in three games and 20th of the season when a 50-metre ball from Johnny Howson went over the champions' defence, allowing him to control it and angle a shot wide of goalkeeper Tomas Kuszczak.
It was the first time Alex Ferguson had suffered defeat in the third round, the stage at which the top clubs enter the FA Cup, since he became United manager in 1986.
"I must admit, I didn't expect that performance," Ferguson told MUTV.
"If you don't start and the other team does, you're always up against it.
"Leeds had a far bigger appetite than us for the game. You need a bit of luck and they got it but they deserved it because they played really well," he added.
United's first lost to lower league opposition since 1984 also gave Leeds a memorable victory at a ground where they regularly used to duel with United for national supremacy before their slide down the leagues.
The 9,000 away fans went wild with delight at the end of a thrilling Cup tie which produced the first big shock of the round after a series of predictable results on Saturday.
"It was a good long diagonal ball from Johnny Howson and nine times out of 10 Jermaine finishes them off and that's what he did," Leeds manager Simon Grayson told ITV.
"We gave ourselves an opportunity to go and win the game from there and with a bit of luck here and there we've hung on.
"I am sure they will be celebrating in Leeds for the next few days," he added.
Deserved Victory
Grayson's men thoroughly deserved their victory, which could have been even greater if Beckford had scored after 78 minutes instead of dragging his shot just wide.
Robert Snodgrass smashed a 25-metre free kick against the United bar two minutes later before goalkeeper Casper Ankergren parried a goalbound effort from Wayne Rooney in stoppage time.
Michael Owen, Dimitar Berbatov and Rooney went close to equalising for United but Leeds, who needed a replay to get past non-League Kettering Town in the last round, hung on for a memorable victory -- their first at Old Trafford since 1981.
Real Madrid to make 20 million pound bid for Vidic
Man Utd cruise past Wolves to go level at top
Manchester United laid low by injuries to backline
Rooney inspires Manchester United to victory
Manchester United slash Chelsea's lead