Patrick Kluivert tapped home what turned out to be the winner after just five minutes but after a shaky start we dominated possession for long spells without reward.
Sky Sports' statistics showed efforts on goal at 12-6 in our favour - 7-2 on target - and Paul Robinson didn't have a save to make until break from Kieron Dyer two minutes from time.
At the other end, Given saved his best for the 67th minute when he first palmed out Robbie Keane's effort from Fredi Kanoute's cut back and got up in time to parry away Jermain Defoe's stinging full volley from the rebound.
Keane looked rightly aggrieved to have a goal disallowed just two minutes from time after Anthony Gardner was penalised for a shove and referee Rob Styles waved away two appeals for penalties with Lee Bowyer appearing to handle in the area, the second, more blatant offence in injury time.
The lads couldn't have given any more but it wasn't enough.
We kicked-off with five changes to the team that started at Southampton last weekend. In came Naybet, Atouba and Pamarot in defence for Gardner, Kelly and Edman, Ziegler replaced cup-tied Reid while Kanoute started up front alongside Defoe in place of injured Mido.
Newcastle came flying out of the traps and after a couple of half-chances, took the lead after five minutes. It wasn't the best of goals for us defensively as both Atouba and King lost out in 50-50 challenges, Shearer broke into the box and cut the ball back for Kluivert to tap in from close range.
Dyer's pace caused Atouba problems - he was booked - and we lived on our nerves for a while but Newcastle didn't seriously threaten again as we grew stronger and stronger.
With Sky Sports TV coverage showing possession at 83-17 per cent in our favour in the latter part of the half, Kanoute forced Given into a low save and flicked Defoe's cross just wide, Ziegler's 30-yard free-kick hit the target and Defoe's crisp shot stung the home keeper's hands.
There was a warning late in the half as Carr's deep cross found its way through to Robert at the far post, his effort blocked by Pamarot, but generally Shearer and Kluivert were kept quiet. - Newcastle certainly didn't create as much as they did in our 1-0 win here back in August.
Newcastle started the second half in similar fashion to the first but after surviving that, the rest of the half was all about us.
Davies might have done better with a volley after 52 minutes, a couple of corners caused confusion in the home defence and then Given's heroics, keeping out Keane and then Defoe within a matter of seconds.
Brown's shot was deflected wide and it was constant pressure for the final quarter, Defoe shot just wide and then forced Given into action again, this time a low save to his right after the striker left Carr in a heap.
Time was running out and it was getting more and more frantic. Bowyer appeared to handle accidently as he fell over the ball in the box and then more controversy as Keane's goal was disallowed two minutes from time as substitute Gardner was adjudged to have pushed in the build-up.
Robinson was forced into action for just about the only time in the game seconds later after Dyer broke clear but, as the clock ticked into injury time, there was still time for two more moments - first Kanoute's header controlled on the line and cleared by Hughes and then an even more blatant handball from Bowyer waved away again by referee Styles.
GUIDE TO THE ACTION
1min: Dyer break down the right, outpaced Atouba, King over to make tackle.
2mins: Bowyer dangerous cross heading for Robert at far post before Naybet's intervention.
2mins: Robert corner headed over by Boumsong.
5mins: GOAL. Shearer broke through 50-50 with King, into box, cut ball back for Kluivert to tap home from close range.
Newcastle 1, Spurs 0
9mins: YELLOW. Atouba for foul on Dyer.
9mins: DISALLOWED. Late flag denies Kluivert after finishing one-on-one.
16mins: Atouba gave ball away, Bowyer quickly fed Shearer, left side of box, low cross cut out by King.
19mins: Our first serious effort, Ziegler's curling 30-yard free-kick taken comfortably by Given.
20mins: Pamarot released Kanoute to byline, took too long to cross and Hughes back to take pace off it, Given out to collect.
21mins: Bramble headed Robert's free-kick over - although ref awarded corner.
24mins: YELLOW. Boumsong for going down under Brown challenge in box.
28mins: Ziegler released Kanoute into box, tried to cut ball back for Defoe and Davies but Bramble there to block.
29mins: Kanoute controlled and spun away from Bramble in one movement from Atouba's pass, left-foot shot not the best, Given took low near foot of post.
35mins: CLOSE. Defoe did well to win possession off Bramble, right side, got to byline and crossed to near post, Kanoute turned towards goal but into side-netting.
37mins: Defoe worked a yard left corner of box, low stinger taken at second attempt by Given.
39mins: SUB. Jenas for injured Bramble.
44mins: Deep Carr cross found its way through to Robert at far post, shot blocked by Pamarot.
Half-time: Newcastle 1, Spurs 0
46mins: YELLOW. Brown for foul on Robert.
46mins: YELLOW. Pamarot for foul on Robert.
49mins: Shearer crossfield pass to Robert, instant cross from left wing inches away from Kluivert.
52mins: CHANCE. Atouba long throw flicked on by Kanoute for Davies, 16 yards out, central, hit volley into ground and wide.
55mins: Ziegler clipped ball over the top intended for Kanoute, Given raced out to claim, grabbed it right on edge of box.
58mins: Carrick's corner created havoc in box, King effort on target blocked, Brown also shot blocked.
63mins: SUB. Keane for Atouba.
67mins: SAVES. Brilliant from Kanoute to get better of Jenas, cut back from byline to Keane, shot parried out by Given, ball went to Defoe who smashed first-time volley straight back in but Given there to tip ball away at full stretch.
67mins: SUB. Ameobi for limping Kluivert.
71mins: Brown shot deflected just wide - home side getting edgy.
72mins: Ameobi break down right, cross intended for Shearer deflected inches wide.
72mins: YELLOW. Ziegler for foul on Dyer.
74mins: Great control from Kanoute from Robinson's clearance, played ball inside to Davies, low cross intended for Keane at near post taken by Given.
76mins: YELLOW. Naybet for dissent.
76mins: Long free-kick from Robinson won by Kanoute, ball fell to Defoe, shot wide.
79mins: SUB. Marney for Pamarot.
80mins: SUB. Milner for Robert.
82mins: SAVE. Defoe skipped around Carr, drove shot in that Given palmed out, ball wouldn't come down for King on rebound and cleared.
84mins: PENALTY? Bowyer appeared to fall accidently on ball in box, nothing given.
87mins: SUB. Gardner for Naybet.
88mins: DISALLOWED. Keane finished after melee from Carrick corner, Gardner penalised for shove.
89mins: SAVE. Dyer break into box, low shot saved by Robinson.
Injury time: OFF LINE. Kanoute headed on Carrick cross, Given failed to meet it, ball fell to Kanoute whose header was cleared off line by Hughes.
Injury time: YELLOW. Davies for foul on Milner.
Injury time: PENALTY? Appeals again for handball against Bowyer waved away.
Injury time: YELLOW. Shearer for foul on Brown.
Full time: Newcastle United 1, Spurs 0
Newcastle United: Given, Carr, Bramble (Jenas, 39), Boumsong, Hughes, Dyer, Faye, Bowyer, Shearer, Kluivert (Ameobi, 67), Robert (Milner, 80). Subs: Butt, Harper.
Spurs (4-4-2): Robinson; Pamarot (Marney, 79), King, Naybet (Gardner, 87), Atouba (Keane, 63); Davies, Brown, Carrick, Ziegler; Kanoute, Defoe. Subs: Edman, Cerny.
An early goal, Shay Given and a disallowed effort late in the game saw an end to our FA Cup dreams for another year at St James Park on Sunday.