Villa looked set for a second consecutive goalless away draw - until Loic Remy wrecked their hopes in stoppage time.
The French striker had wasted a glorious chance in the 88th-minute, somehow firing against the inside of the post when presented with an open target.
But he left Paul Lambert's men feeling totally deflated as he drove home Newcastle's winner in the second minute of added time.
It was a bitter blow for Villa, who have not won at St James' Park for nearly nine years but looked perfectly capable of taking a point on this occasion.
They overcame a hesitant start to dominate for long spells of the opening half.
And even though they created very few openings after the break, a stalemate looked certain until Remy pounced at the death.
Villa were largely on the back foot for the opening 15 minutes, although their defending was sound in the face of Newcastle's early onslaught.
Brad Guzan made a couple of important saves, holding Remy's low drive before diving to keep out Papiss Cisse's curling effort.
He was unable to hold that one but fortunately Nathan Baker was on hand to hook the ball away for a corner.
Moussa Sissoko also had a shot deflected wide during that early spell, while Villa's best attempt was a fourth-minute free-kick from Leandro Bacuna which wasn't far off target.
Baker produced a couple of excellent headed clearances, but the visitors suddenly came to life with a positive spell in which they could have gone ahead.
Karim El Ahmadi twice found good positions through the right channel, initially driving across the face of goal following Andi Weimann's fine through ball and then sending an angled low drive just beyond the far post.
Then Gabby Agbonlahor found his range, first collecting Fabian Delph's pass for a shot which was pushed out by Tim Krul and then finding space for a rising drive from nearly 30 yards which only just cleared the bar.
In the 26th minute Bacuna tried another of his free-kick specials after Agbonlahor had been brought down.
This time he went for the other side of goal but Krul anticipated it well, moving quickly across his line to palm the ball away.
Villa were now producing the better football and on 35 minutes Agbonlahor made another strong run before seeing his shot strike a defender and go behind.
Having been the better side for a lengthy spell, though, the visitors twice breathed a sigh of relief just before half-time.
Remy curled a free-kick narrowly wide in the 43rd minute and in stoppage time Cisse fired over from a good position after his striking partner had knocked the ball inviting across goal for him.
There was no such threat during a low-key start to the second period, neither side managing to create a clear-cut opening until Yoan Gouffran dragged a shot wide of the far upright in the 53rd minute.
Right-back Paul Dummett also ventured forward to send a left-foot shot just too high before Guzan was called into action, holding Cheik Tiote's 66th-minute drive.
Villa had rarely been in the game as an attacking force since the break, although El Ahmadi had a shot charged down before Delph fired well off target.
But the home side were soon pressing again, and Guzan made an outstanding save in the 78th minute, diving to tip away a fierce low drive from Remy.
Remy was guilty of a shocking miss in the 88th minute, sending a low shot against the inside of the post when it looked easier to score.
But he had the final word in stoppage time, turning sharply to send an unstoppable left-footer past Guzan from 10 yards.
Newcastle: Krul; Debuchy, Williamson, Coloccini, Dummett; Sissoko, Anita, Tiote (Gosling 89), Gouffran; Remy, Cisse (De Jong 72). Unused subs: Elliot, Mbiwa, Haidara, Ameobi, Taylor.
Villa: Guzan; Bacuna, Vlaar, Baker, Bertrand (Bertrand 76); El Ahmadi, Westwood (Sylla 60), Delph; Agbonlahor, Benteke, Weimann. Unused subs: Steer, Clark, Albrighton, Tonev, Holt.