A late goal from Jonjo Shelvey sent the game to penalties after Tristan Abrahams opened the scoring for Newport, however Brandon Cooper fired his penalty over the bar.
Story of the game
It was the visitors who had the game's first chance, the ball fell kindly for Sean Longstaff, whose effort failed to test Nick Townsend, and goes over from 30 yards.
Ryan Fraser was then sent down the right, his cross found Andy Carroll on the edge of the area, but his poor touch as Newport cleared the danger.
Soon after the hosts took the lead, Scott Twine unleashed an hopeful drive from 25 yards which dipped over Mark Gillespie and struck the bar, before Abrahams reacted the quickest and his effort, which skid across the surface saw Gillespie palm it into his own net.
Newcastle tried to respond after falling behind, when Fraser raced down the right again, his cross deflects off a defender before looping towards goal which saw Townsend tip behind for a corner, which Newport managed to clear.
Newcastle continued to try and get back on level terms, Jacob Murphy did a nice pivot in midfield which allowed him to get a shot away, forcing Townsend into a smart stop, before Murphy tries another decent effort which Townsend also saves.
Newport then went close after Matt Dolan sent a free-kick over the wall, but it goes a yard or so wide with Gillespie looking to have it covered, at the other end, Longstaff whipped in a lovely delivery into the area, which Carroll attacked, it fell to Fraser at the back post who can't send his effort on target.
Newcastle went close again five minutes before half-time, Javier Manquillo sent in a cross from the right, Fraser heads it down into the path of Shelvey, who failed to get a decent connection and the Townsend claimed the ball easily.
Newport could have had a second goal before the break, Liam Shephard does brilliantly to cushion the ball into the path of Scot Bennett, however, his first-time effort goes inches past the post and bar.
The last chance of the first half fell the way of the hosts, Manquillo's poor clearance sent Shephard's cross straight to Padraig Amond in the visitors' area, his first touch is great, however, his effort was poor sending it over the bar.
The first chance after the restart, fell to the visitors, Fraser sent in a deep cross which reached Murphy at the back post, his volleyed effort towards goal was blocked by Mickey Demetriou, before it went behind for a corner.
Newport's first chance after the break fell to Twine who managed to get away from Longstaff and fire an effort on goal, however, it was a tamed effort which Gillespie claims with ease.
Townsend then made two great saves to keep the hosts in the lead, Fraser got in behind which the keeper manages to thwart his effort before he denied Miguel Almiron with the follow-up effort.
There were serious concerns for Newport when both Demetriou and Bennett clashed heads, which looked nasty however, both players were able to continue.
Newcastle went close to an equaliser, immediately after coming on for Almiron, Callum Wilson was involved, linking up with Murphy, who went alone despite Wilson being in space, and the winger dragged an effort wide.
Newport then went close after some good play involving Josh Sheehan and Twine combine nicely before feeding Ryan Haynes on the overlap, whose low driven cross was deflected behind for a corner, which fell to Amond whose header went away from goal.
Fabian Schar went close for Newcastle, following a corner which bobbled in the area as it reached the centre-back in the area, before the ball struck his chest before drifting wide of the target, before Shelvey teed-up Murphy on the edge of the area, whose effort goes agonisingly wide of the target.
Fraser got in behind for the visitors and just about as he thought he was about to score, Brandon Cooper with a superb last-gasp challenge to send the ball behind for a corner, which was cleared.
Fraser got played in behind again, Demetriou looked to clear his cross but failed to connect with the ball, Murphy was caught off-guard and he bundled his effort into the arms of the grateful Townsend.
Just as it looked like Newcastle couldn't find away past Townsend, Shelvey worked his way onto his right foot from around 18 yards and fired an unstoppable effort into the top corner to level the scores.
Townsend makes a another good save to deny Murphy after a very decent effort following the ball sitting up kindly for him.
Shelvey saw a free-kick from 25 yards blocked by the wall as the visitors tried to win the game late on, before two clearances off the line in the dying moments by Newport sent the game to penalties.
Newcastle score through Callum Wilson. 1-0
Newport score through Mickey Demetriou. 1-1
Newcastle miss after Joelinton sees his penalty saved. 1-1
Newport score through Tristan Abrahams. 1-2
Newcastle score through Fabian Schar. 2-2
Newport score through Josh Sheehan. 2-3
Newcastle score through Jonjo Shelvey. 3-3
Newport miss after Ryan Taylor sees his penalty saved. 3-3
Newcastle score through Jacob Murphy. 4-3
Newport score through Matt Dolan. 4-4
Newcastle score through Sean Longstaff. 5-4
Newport miss after Brandon Cooper fires over the bar. 5-4
Newcastle win 5-4 on penalties
Bruce won't be delighted despite Newcastle scraping through on penalties
It was a poor showing from Newcastle, despite having chance after chance they had to wait until the 87th minute to get on the scoresheet through Shelvey before seeing Newport's Brandon Cooper firing over the bar to send the Magpies through.
Although, Newcastle went through, manager Steve Bruce won't have been happy with how many chances his team wasted on numerous occasions throughout the game, although some good defending from Newport to keep out the chances Newcastle created.
Newport County: Townsend, Cooper, Dolan, Demetriou, Shephard, Bennett (Willmott 80), Sheehan, Twine (Collins 90), Haynes, Abrahams, Amond (Taylor 80).
Substitutes (not used): King, Baker, Janneh, Ellison.
Newcastle United: Gillespie, Manquillo, Krafth (Schar 71), Fernandes, Lewis, Shelvey, S Longstaff, Murphy, Almiron (Wilson 62), Fraser, Carroll (Joelinton 62).
Substitutes (not used): Darlow, Hayden, Hendrick, Anderson.
Referee: John Brooks (Leicestershire)