Despite defender Gaetano Berardi putting the visitors ahead after nine minutes, Leeds failed to take control of the game in which Newport went on to show their quality.
Newport piled on the pressure, creating multiple chances throughout the game, making it difficult for the visitors, using their poor pitch to their advantage.
The Welsh sides efforts paid off late in the game as Leeds defender Conor Shaughnessy failed to deal with Nouble's low cross, with the ball going into the back of his own net, making the scores all square.
Then with just a minute left of normal time to go, a corner swung in by Willmott was met by substitute Shawn McCoulsky, who climbed high to head the ball past goalkeeper Andy Lonergan, sending the League Two side into the next round of the FA Cup.
This FA Cup third round tie saw only the third time these two clubs had played against each other. The first meeting was also a third round FA Cup fixture, with Newport County running out 3-1 winners in Yorkshire.
However, Leeds were victorious the last time the two sides had gone head to head, securing a 5-1 win over the Welsh side in the Carabao Cup at Elland Road earlier on this season.
Can Leeds' nine changes progress into fourth round?
Newport County named an unchanged line-up from their 2-1 win against Exeter City at home on New Years day.
Meanwhile Thomas Christiansen made nine changes to the side that drew 0-0 against Nottingham Forest at Elland Road on Monday.
On loan left-back Cameron Borthwick-Jackson was named in the starting 11 for Leeds despite rumours that Leeds and parent club Manchester United are in talks over cancelling his season-long loan deal.
The other eight changes saw strikers Grot and Lasogga, midfielders Cibicki, Sacko and Klich, defenders Shaugnessy and Anita, and goalkeeper Lonergan step into the fold, playing in a 4-4-2 formation. Full-back Berardi stepped into the centre-back position and was given the captains armband for only the second time in his Leeds career.
Good start for the visitors
The first chance of the game came just 10 seconds in as Jay-Roy Grot found himself one on one with the goalkeeper form a mistake at the back, but his effort went straight into Day's hands who was quick to react.
Despite the early chance for Leeds, the home side played some good football and created a few chances of their own.
However, it took just nine minutes for the visitors to get their noses in front. A poor clearance fell to the feet of Gaetano Berardi who tried his luck from twenty-five yards out. His shot flew past the Newport County goalkeeper, putting the Whites ahead. The goal was Berardi's first ever career goal.
Leeds struggle under difficult circumstances
Newport County didn't seem fazed at all by the side who are two leagues above them going a goal ahead. It was not a pretty game to watch to say the least, and the Welsh side made it difficult for the visitors using their uneven pitch to their advantage. Leeds struggled to take control of the game despite leading, with the home side creating a handful of chances for themselves against a wobbly Leeds back line.
The most notable chance came just six minutes after the visitors took the lead, as a Newport corner was swung in and not dealt with by Leeds. The ball fell to the feet of Newports top scorer Padraig Amond who's shot was bundled off the line.
Newport on the front foot going into the second half
Apart from the odd shot and a weak free kick from Cibicki, Leeds never settled down and took advantage of gaining an early lead.
Newport kept testing a very nervous Leeds side and created a lot of chances throughout the first forty-five minutes. The home side were using their wing-backs well when attacking, with the two strikers Amond and Nouble causing all sorts of problems for the Leeds defence.
The Whites managed to hold off Newport, and it was 1-0 at the break.
The home side continue to impress
Just like the first half, Leeds got the first chance of the second half on forty-eight minutes. Cibicki's cross from the left was met by Lasogga who headed wide under pressure.
Two minutes later however, the nervousness of this Leeds side showed as Sacko's back pass almost fell to Amond, but goalkeeper Andy Lonergan reacted quickly to deal with it.
The Welsh side kept piling on the pressure as Amond's overhead kick hit into the side netting.
Leeds then created a few chances for themselves but failed to convert. The inexperience of striker Jay-Roy Grot showed as he lashed his shot over the bar on sixty minutes.
Leeds turn to captain Cooper
A credit to Newport's effort as Leeds turned to their regular captain Liam Cooper who replaced Cameron-Borthwick Jackson. Berardi moved to full-back position with Liam Cooper filling in at centre-back.
Liam Cooper showed just why Leeds brought him on as Newport kept floating balls into the visitors' box. A high ball found Nouble at the far post. It almost sit up perfectly for the striker to smash it in but Cooper intervened.
The Welsh side came close again after sixty-eight minutes. An unmarked Labadie hit his volley just over the bar.
A rare chance for Leeds however down the other end of the field. Lasogga twisted and turned on the edge of the Newport box before firing over the bar.
Newport's pressure pays off
Newport had been the better team for the the majority of the game, and their efforts payed off when Nouble's low, hard cross from the right smashed off of Leeds defender Shaughnessy and into the back of the net. 1-1 on seventy-six minutes.
Leeds crumble under pressure
Since levelling the scores, Newport continued to pile on the pressure in search for a what would be a well deserved winning goal.
A cross from the left flicked off Shaughnessy, with the finding Nouble who headed over. Then substitute Paul Hayes created his first chance of the game ten minutes later, his shot looping just over the crossbar.
Then with just a minute left of normal time Newport swung in a corner, and fellow substitute Shawn McCoulsky leaped high to head home. A free header which sent the Newport fans and players into ecstasy.
There was controversy afterwards as Leeds substitute Samuel Saiz was shown a red card by referee Mike Dean. With Leeds down to ten men and now losing 2-1, it was a mountain to climb if the visitors, who had struggled throughout the game, wanted an equaliser to take the tie to a replay.
Newport County produce a cup upset as they knock out Championship side Leeds United. Michael Flynn will now see his team's name in the fourth round of the FA Cup.