The Frenchman struck with 19 minutes remaining to snatch all three points and relieve some pressure on under-fire manager Alan Pardew in the process.
Below, you can see how the drama unfolded with Sports Mole's live commentary of the clash.
2.01pmGood afternoon ladies and gentlemen and you're very welcome to Sports Mole's live text commentary of Newastle United's Premier League clash at home to Leicester City.
2.04pmHe has won the Johnstone's Paint Trophy. He has won a Championship playoff final. He has guided one of his former clubs to an FA Cup final. Can you tell who it is yet? Why it's Alan Pardew of course, the beleaguered Newcastle manager who might be tempted to bracket this afternoon's visit of Leicester City with the above events in terms of importance.
2.07pmThis is because Newcastle come into this clash without a victory this season and with just one win in their last 15 Premier League outings - and 18th in the table! Yep, anything but a victory for the winless Magpies and owner Mike Ashley might just have to swing the axe that he has been gripping for a number of weeks now.
2.10pmIt's no exaggeration to suggest that this may be Pardew's last game if Newcastle don't win, but three points could, and should, be on the cards today. Leicester, despite their early-season heroics, have taken just one point from their last two games and Newcastle will want to further slow that momentum by winning today.
2.12pmIncidentally, this is Pardew's 700th match as a manager so let's hope for his sake he marks this milestone in winning fashion, eh?
2.14pmRight, let's get you some team news to chew on. Firstly, how's about checking what the Sports Mole lads had to say on this one? Go on and I'll see you in a few.
2.17pmLEICESTER CITY XI: Schmeichel; De Laet, Konchesky, Drinkwater, Morgan, James, Albrighton, Schlupp, Moore, Cambiasso, Ulloa
2.18pmNEWCASTLE UNITED SUBS: Elliot, Haidara, Anita, Abeid, Cabella, Perez, Armstrong
2.19pmLEICESTER CITY SUBS: Hamer, Hammond, Vardy, King, Knockaert, Wasilewski, Nugent
2.22pmRight let's start with Noo-cass-al and I can tell you that Tim Krul starts in the net after previously being considered a doubt due to an elbow injury. Steven Taylor returns to partner captain Fabricio Coloccini at the heart of defence. Jack Colback and Cheick Tiote line up in the middle of midfield, while Gabriel Obertan and Yoan Gouffran provide support from the wings. In-form Papiss Cisse, meanwhile, continues up front. We'll have a closer look at him a little later.
2.25pmOn to the Foxes now and Nigel Pearson makes three changes from the 2-2 draw with Burnley last time out. Same back four of Richie De Laet, Paul Konchesky, Liam Moore and Wes Morgan, but Matty James, Esteban Cambiasso and Marc Albrighton all come into the midfield. As ever, Leonardo Ulloa spearheads the attack.
2.27pmWhat do we make of those teams then? Interesting to see how Cambiasso does. The veteran midfielder has endured a lukewarm start to life at Leicester; big performance in the 5-3 win over Manchester United but struggled the following week against Crystal Palace. He comes up against Jack Colback and Tiote today, so anything less than a black eye and a few sore ribs and it's a positive.
2.30pmWouldn't it be great to see Papiss Cisse rediscover the form that he showed in his early days at Newcastle? Cisse has almost single-handedly kept Pardew in the job after scoring all four goals in the Magpies' recent come-from-behind 2-2 draws with Swansea City and Hull City. He scored 12 times in his first 13 games for Newcastle, and Pardew will desperate to see him scale those heights once again. Nobody else will, will they?
2.33pmThey've only scored seven times in the league so far, and Cisse has four of them! Mike Williamson, Rolando Aarons and Daryl Janmaat scored the others - and those came in the same game, a 3-3 thriller with Crystal Palace. Cisse is massively important to this team folks.
2.37pmLooks like we're in for a delay at St James' Park, my friends. "Turnstiles at SJP are currently closed due to safety concerns relating to panels surrounding the LED screen. We apologise for the delay." I reckon the delay is down to that very large Newcastle fan (you know the guy) getting stuck in the turnstiles...
2.40pmAnyways, let's carry on and we'll have more info on the delay soon. Leicester striker Leonardo Ulloa also has to lace up his shooting boots once more. The Argentine won plenty of plaudits for his five goals in as many games, but there are worrying signs that those goals have dried up after failing to score in his last three outings.
2.43pmIt's not unusual for a Premier League newcomer to blaze trails early on, and it's not uncommon to see their influence and goals diminsh as the season progresses. Are we seeing this from Ulloa? Time will tell. He's key to a Leicester win here.
2.46pmHere's the latest news on this delay, but we're still unsure as to what time this one will go ahead. Newcastle wrote on Twitter: "We will bring you updates including any information on turnstiles and a revised kick-off time as soon as we can. Thank you for your patience"
2.48pmDID YOU KNOW? While we await further news from St James', have a stat on me: Leicester have not won here since the 1999-00 campaign. Goals from Tony Cottee and Robbie Savage gave them a 2-0 win over the Magpies that day. Uriah Rennie was the ref. Remember him? He's now a very rich man after inventing heartburn tablets. That is not true.
2.51pmNothing is going right for Newcastle these days, is it? When it rains it pours.
2.54pmSTAT! Here's another decent stat to whet the appetite and I can tell you that Newcastle are the only team in the league yet to score first this season, which is remarkable. I fancy that will come to an end this afternoon, though - if it goes ahead. Apparently the giant scoreboard in question was seen swaying in the wind. Would you risk it? Me neither.
3.01pmStill awaiting further news from the club itself on the state of play. Rumours of postponement have gathered momentum on Twitter in recent minutes but Twitter isn't reliable at the best of times, is it? Still, it's a massive screen that might need to be removed if this kicks off this afternoon - and removing it might take a while!
3.10pmSo, there we have it folks. Kickoff at St James' is now scheduled for 4pm after issues with a giant screen inside the ground caused health and safety concerns. We'll be back shortly before kickoff so don't venture too far. Until then....
3.45pmWelcome back ladies and gentlemen. The issue with the giant LED screen that caused this hour-long delay has been resolved and we're about 15 minutes from kickoff now. Hopefully.
3.47pmThere's also a change in the Newcastle lineup to tell you about as Tiote picked up a knock and is replaced by Vurnon Anita. One of those days for the Magpies, isn't it?
3.50pmWill the delay favour any team? Yes, and it may possibly benefit Leicester. Newcastle fans would have travelled to St James' Park prepared to continue their vocal opposition of Pardew if necessary, which is never good for the players. However, this hour-long wait will have made the atmosphere even more tempestuous and they're probably at boiling point. The slightest thing might tip the home fans over the edge into a full-scale boo-athon. That's the worry I'd have.
3.52pmWith that in mind, let's lodge a pre-match prediction, shall we? Prior to this delay I had fancied Newcastle to temporarily silence the boo boys and pick up a first league win of the season. Now? I'm not so sure. 2-1 Leicester. Ulloa with the winner. There you go. Eight minutes to go!
3.54pmThere's one fan inside St James' Park with a Newcastle-themed hard hat! We could've done with him about an hour ago to scale the scaffold and tighten up that dodgy scoreboard.
3.56pmRight, both sets of players make their way onto the field and exchange the customary pre-match handshakes ahead of this one. Nothing can go wrong now, can it?
3.59pmJust one hiccup to tell you about as the players are forced to change halves, having already settled. I used to hate having to do that in my brief football career. Kickoff is imminent now.
0 minKICKOFF! Aaaaaaaaaaaaand we're finally off at St James' Park ladies and gents. It's been an hour in the making, but we're underway. Let's go.
1 minSloppy play by Colback as the midfielder concedes a really cheap throw-in. Newcastle have it again though after Leicester lose possession.
3 minCambiasso, Leicester's deepest midfielder, is lucky after playing a sloppy ball outside his own box but he gets away with it.
5 minFirst set-piece opportunity of the game after Paul Konchesky conceded a corner, but Liam Moore does well and clears Colback's delivery. It's been a good start for Newcastle.
8 minCHANCE! This should've been 1-0 to Newcastle folks. Defender Coloccini joins a Newcastle counter-attack as Obertan carried the ball forward, and the Frenchman pulled back for his Argentine counterpart but Coloccini strokes wide of the mark from in the box. Big chance.
11 minGood defending from Paul Dummett, who thwarted Richie De Laet's surging run from right-back. Leicester yet to really offer anything in the final third.
14 minLikewise, Liam Moore shows fantastic strength to shield the ball there and then sends Cisse flying when trying to wrestle it from him. Moore and Morgan will have a big say in Leicester's chances here.
16 minExcellent ball from Jack Colback there, as his over-the-top ball finds Cisse in the middle. The striker then finds Obertan on the wing, but the Frenchman's cross is tame and Leicester get it away. The final ball needs improving, from both sides.
18 minNewcastle fans are on their feet, but there hasn't been a goal. They're standing to applaud Jonas Gutierrez, who is battling testicular cancer. His number is 18, hence the 18th-minute applause.
20 minSHOT! Dummett intercepts a Leicester pass before launching a fierce strike at Kasper Schmeichel, who caught it comfortably enough.
21 minCHANCE! Oh dear. This one makes Coloccini's earlier effort look difficult. Ulloa holds the ball up well deep in Newcastle's half, before squaring to the unmarked Matty James who, with just Tim Krul to beat, passes straight into the hands of the Dutchman. Shocking finish.
22 minBOOKING! Liam Moore goes into the book for a strong challenge on Obertan. Good decision by referee Martin Atkinson.
24 minNewcastle really bossing the possession stakes but, aside from that Coloccini chance, little to write home about.
27 minPENALTY APPEAL: Daryl Janmaat might be slightly lucky not to concede a penalty here, after inadvertently taking out Ulloa before he could reach a teasing cross. The Argentine is still down in the box.
30 minGoalkeeper Tim Krul taking a bit of stick here because he's kicked it out of play for about the fifth time already. He looks to be searching for Obertan on that right wing every time, but he finds Pardew and his coaching staff.
32 minIncidentally, Newcastle have not yet taken the lead in a league game this season. It doesn't bode well, does it? This one could go either way; very little between the sides.
34 minBOOKING: Ulloa also booked for a late challenge on Steven Taylor. Probably the right decision.
36 minCisse's eyes lit up there after finding himself through with Schmeichel, but he drags his shot well wide of the mark. However, Atkinson blew the whistle for a previous foul on Liam Moore.
38 minWe're about seven minutes from half time and I'd be surprised if it's not 0-0 at the break. Both have had excellent chances, but we're still goalless.
40 minOFF THE BAR! Just as I say that, Leicester come within the width of the crossbar from going ahead, as Marc Albrighton's deep cross loops over Tim Krul and cannons off the woodwork. Not really a chance because it was an accident, but that's as close as we've come.
43 minCLOSE! Cisse goes close to earning Newcastle a half-time lead as his shot is deflected off the leg of Moore and loops onto the roof of the net. Looking like stalemate at the break.
4.50pmThat's all she wrote in this half, my friends. Fabricio Coloccini and Matty James spurned the best of the chances for their respective teams but we're still goalless. We had to wait an hour for this but it hasn't really been worth waiting for so far.
4.55pmNewcastle fans may be disillusioned by their club at the moment, but a penny for the thoughts of their North-East neighbours Sunderland, who have just shipped EIGHT, yes EIGHT goals away to Southampton. Elsewhere, Hull City held Arsenal to a 2-2 draw at the Emirates. Chelsea beat Crystal Palace. West Ham beat Burnley and for everything else just click here!
4.58pmWe thought the hour-long delay might irk an already-frustrated bunch of Newcastle fans, but to their credit they have shelved their opinion of Alan Pardew for the moment and really got behind their team. They'll need more of the same in the second half, but you wonder if the fans' propensity to protest may surface as the game goes on if the score remains the same.
45 minAaaaaaaaaaaand we're back. Leicester, playing from left to right now, get us back underway. It's a massive 45 minutes for Newcastle - who are still chasing their first win, incidentally.
48 minGood outside-of-the-boot ball from Cisse but Obertan didn't show enough hunger to get into the box. It was a fantastic cross but nobody there to tuck it away.
50 minCLOSE! This is so close. Moussa Sissoko takes aim from outside the box, but it shot takes a deflection off Liam Moore and loops over the outstretching Schmeichel but it drops just wide of the mark. Good start by the hosts.
52 minOPEN GOAL! Oh my word Papiss Cisse has just missed an open goal. The striker capitalised on a slack back pass from Konchesky before rounding Schmeichel but, rather than rolling the ball home, thrashed at it and found the side netting. When it's not your day it's not your day.
54 minSAVE! Newcastle really on top now as Schmeichel pulls off a fantastic save to palm away Jack Colback's angled free kick. They need to take one of these chances.
55 minSubstitutions: Couple of subs to tell you about now as Schlupp and Albrighton make way for Vardy and Nugent. Decent subs by Leicester.
57 minSUBSTITUTION: Looks like Newcastle are weighing up a sub now aswell, with Ayoze Perez looking poised to come on. Yep, the South American replaces Vurnon Anita.
60 minShocking from Cambiasso, whose delivery has been woeful all evening. The Argentine has a good chance to whip in a decent ball from a free kick, but it's well over-hit and trickles out for a goal kick.
63 minCambiasso whips in a corner now but yet again fails to find a Blue shirt. However, he plays a fine layoff in behind Dummett there a moment ago and we've got another corner coming up.
65 minLeicester did well to weather that early Newcastle storm, but they still haven't done much up the other end, with Matty Smith's chance still their stand-out opportunity.
68 minPerez fashioned a decent chance there but, instead of shooting from just outside the box, squared to Papiss Cisse, who was offside. That's why he's yet to score for the Magpies.
69 minGood defensive work from Jack Colback, who cuts out David Nugent's teasing cross in the nick of time. It looked to be heading toward a Blue shirt in the box.
72 minWe've finally got a goal from St James' Park and it's Gabriel Obertan, who picks the ball up from Papiss Cisse before evading a number of challenges on the D before finding the bottom corner from just outside the area. Decent strike, that might have been deflected. He won't care, nor will any Newcastle fan inside the stadium. 1-0.
74 minIncidentally, that was the first time that Newcastle have scored first in a game this season. Will it lead to their first win of the season? We'll know in about 16 minutes.
76 minOh dear. A better first touch from Ulloa and he's through on goal with Tim Krul. Fine margins for Newcastle.
78 minSUBSTITUTION: Last throw of the dice for Nigel Pearson as Anthony Knockaert replaces Cambiasso. Plenty of attacking options on the field now for the visitors.
81 minThere's about nine minutes left here folks and, as it stands, Newcastle are on course for their first league win of the season. Can they hold out? Massive last 10 minutes for Alan Pardew, whose job is on the line.
83 minSAVE! Leicester really applying the pressure now and they force Tim Krul into a key save, as Danny Drinkwater fires straight at the Dutchman from inside the box.
85 minCHANCE! Well that should be that, but it's not. Perez swings in a fine cross for Papiss Cisse, who heads into the ground and his header bounces up and over the bar from about five yards. Massive chance.
87 minPerez has been decent since he has come on and he has just won a corner now off Wes Morgan. That'll eat up a few minutes.
89 minIn the words of Moloko, the time is now if Leicester want to nick a point from this one. There's one minute of normal time left but it's not happening for them.
90 minTHREE MINUTES ADDED ON: Leicester, who won a soft free kick, are going to launch the ball forward now...
92 minGood free-kick chance for Newcastle now after Perez goes down under a challenge from Konchesky. It's right beside the corner flag. Time for operation 'run the clock down'.
5.52pmThat's it. Newcastle claim their first Premier League win of the season, courtesy of Gabriel Obertan's goal 19 minutes from time. It's been a long time coming - and even longer by the hour-long delay - but they finally have it.
5.53pmSurely a weight will be lifted from the shoulders of Alan Pardew, who has found himself under intense pressure to get results in recent weeks. He's got one today so that should at least buy him a little more time at St James' Park.
5.53pmWell, that's all from us, my friends. Thank you very much for joining us and stay tuned for analysis and player ratings of this one. Until next time....