Watford had suffered six straight league defeats following a 4-1 victory against Manchester United in mid-November, whilst the Geordies had only won once this season.
After an eventful first half, the sides went back down the tunnel at half time goalless. Joelinton went closest by hitting the post before knocking another shot just wide.
The stalemate was short-lived in the second, however. Allan Saint-Maximin capitalised on a mistake by Hornets left-back Jeremy Ngakia to put Newcastle in front five minutes after half time, firing the ball past Ben Foster's near side.
After a spate of great chances for Watford to equalise, they finally did with two minutes left on the clock. Kiko Femenia carved a beautiful ball into the centre of the box, to which Joao Pedro rose above Jamaal Lascelles and placed effortlessly past Martin Dubravka.
The result keeps Watford one point above the relegation zone and keeps Newcastle inside the bottom three. Here are the key takeaways after an entertaining battle at the bottom.
Chances have to be finished off from both sides
Following Saint-Maximin's goal, Newcastle sat back and allowed Watford to come at them.
The visitors did just that. Yet although the forward play was the nicest seen from the visitors since their 2-1 defeat against Chelsea at the start of December, they failed to be clinical enough.
First, King ran through on goal down the left side following a well-weighted ball from new signing Edo Kayembe; but a poor first-touch meant the result was a comfortable save from Dubravka.
Second, was a golden chance with 25 minutes to go. Dennis capitalised on a dreadful pass from Jamaal Lascelles, running from the half way line to the edge of the area. He found Moussa Sissoko on the right, in acres of space, but all he could do was fire over the bar with a clear-sight of goal.
Had Pedro not scored, these would have been much rued chances. Nonetheless, the failure to take three points from Tyneside may prove cynical should Claudio Ranieri's outfit fail to take three points from fellow strugglers Burnley or Norwich City over the next week. The importance of the 20-year-old's goal cannot be understated, however - especially as a morale booster.
But for Eddie Howe's side, the situation is worse still. If the Hornets do take points in the next week, the richest club in the world will be staring relegation in the face.
This is the ninth time the Magpies have failed to close up a game from winning position. All those games could prove costly and, being the nature of Saturday's opposition, especially this one.
Joelinton had two great chances in the first-half which he should have done better with, while new signing Chris Wood was noticeably quiet. The 6-foot-3 striker nonetheless headed over twice in the first forty-five from a decent position.
All in all, something needs to change fast for Howe's outfit. Yet Watford have to be more clinical as well.
Individual errors prove costly on the day
Despite another positive performance from the Golden Boys - especially in the second-half - they are still prone to individual errors which ultimately cost them all three point in the North-East.
This time, it was a mistake at left fullback. The ball fell to Jeremy Ngakia who couldn't sort his feet out and allowed Saint-Maximin to pounce with a commanding strike from the edge of the box.
Aside from the error, Ngakia had a good performance for the Hornets. Ranieri will only hope that the error does not knock his confidence.
Although West Ham deserved their 4-1 victory at Vicarage Road in the December, their goals were often a cumulation of errors from the hosts. Meanwhile, defeat against Tottenham Hotspur was a result of a late and lazy challenge on the edge of the area, providing Spurs with their opportunity to win them the game.
These errors continue to cost Watford but the same can be said of Newcastle.
Partly due to a high press from the visitors, the Magpies often gave away possession carelessly which could well have lost them the game had Watford been more clinical.
Lascelles was at fault for Sissoko's golden opportunity, placing the ball straight to Dennis' feet; whilst Pedro's goal came from Chris Wood losing possession after some weak hold-up play.
These errors and lost-possession, which were numerous in their count on Saturday, are part of the big reason why both teams sit where they do in the Premier League at the moment.
Watford debutants impress
Nonetheless, individual mistakes can become less so with squad improvements.
With three debutants on the field for the Hornets, it was a question as to how each of them would perform. In some brightening news for the club, they all impressed.
Hassane Kamara, signed from Nice, was very solid at right-back. He was strong defensively, committed to winning the ball and intercepting the Newcastle forwards. Attack-wise, he also looked good; being confident on the ball and making some good dribbles.
Brazilian Samir, transferred over from fellow Pozzo-owned club Udinese, was a much needed Centre-Back. He looked good and, although not having much to do, appears to give some sort of command over the six-yard area. Whether he is enough will remain to be seen, but it was good news overall.
Finally Edo Kayembe came into the side replacing Imran Louza who is on international duty for Morocco. He played some good passes and, together with summer-signing Sissoko, could help establish a commanding midfield.
Despite a need to be more clinical and cut-out individual mistakes, Watford can be optimistic heading into two more season-defining games.
For Newcastle, the mood may be more negative. Their next game is away at Leeds United who sit just above the four strugglers at the bottom and a win for Howe's side is long overdue.