Paul Scharner's late strike handed West Brom victory as Newcastle failed to win for the sixth successive league match.
Peter Odemwingie gave West Brom the lead when he fired in from 16 yards.
Demba Ba equalised with a superb 20-yard free-kick before the Baggies again went ahead when Gareth McAuley nodded in from close range.
Ba made it 2-2 with a firm shot, but Scharner's volley ensured that West Brom won at Newcastle in the league for the first time since 1977.
It was heartbreaking for the Magpies who, having twice fought back and having created several chances, were dealt their second home defeat this season and their fourth loss in the last six matches.
And a stat the owners would prefer to gloss over, is that they have not won at the Sports Direct Arena since the ground's name was changed from St James' Park on 9 November.
The only stat West Brom were interested in was securing their second successive win - one that was built on great defensive work and fuss-free counter-attacking.
Both sides, however, deserved pats on their backs after delivering a thoroughly entertaining spectacle.
Midfielder Chris Brunt and striker Peter Odemwingie were the big threats in attack for the Baggies while, once again, Senegal striker Ba was the star man for Alan Pardew's team. All three were key to the goals in the first half.
DID YOU KNOW?
Newcastle, who had the best defensive record this season, have now conceded 14 goals in six games
The Baggies pair combined for the opener, when Brunt threaded a pass through to Odemwingie with the outside of his foot. The Nigerian looked up before drilling his shot past Tim Krul.
Ba, who scored his 12th and 13th of the campaign, then levelled for Newcastle when he took responsibility for an attacking free-kick, in the absence of Ryan Taylor, and curled his shot firmly past Ben Foster.
But, just before half-time, the Baggies again seized the advantage when playmaker Brunt swung a free-kick to the far post, which was headed back across the six-yard area by Jonas Olsson and nodded into the net by McAuley.
West Brom spent much of the second half trying to protect their lead under severe pressure from the Magpies.
Slovenian Haris Vuckic, 19, impressed on his full league debut. He hit the bar and forced a greeat save from Foster, while Ba went close to scoring what would have been the 20,000th Premier League goal with a 20-yard strike that flew a fraction wide.
He missed that landmark as Marc Albrighton of Aston Villa scored first in their match with Arsenal .
But Ba brought Newcastle level again when Hatem Ben Arfa teed up his team-mate to fire high past Foster from just inside the area.
West Brom's best chance during that early period of the second half fell to Shane Long, who rounded Krul but struck the bar with his shot.
But, with five minutes of normal time remaining, the Baggies grabbed what proved to be the winner. Long's looping cross from the right found Odemwingie who headed back into the path of Scharner. The Austrian stretched out a leg and volleyed in.
West Brom manager Roy Hodgson:
"It was remarkable to come back again and get the third goal. We squandered good opportunities in the first half, although they weren't clear-cut.
"We were solid defensively and worked very, very hard. If Shane [Long] had not hit the crossbar then life would have been more comfortable.
"It's been misfortune more than anything as to why we have not won as many points at home as we have away."
Newcastle manager Alan Pardew:
"You would have expected us to win after we got back to 2-2. They had a bit of fortune for their third goal.
"We were cheap with possession at times.
"Maybe the win is playing on our minds - we want that under our belts. We were desperate at times. We have to be more patient and more controlled. We were throwing numbers forward and got caught at times."
Live Text Commentary
Full Time The final whistle goes and the game is over.90:00 +3:22
Centre by Hatem Ben Arfa, clearance by Gareth McAuley.90:00 +2:36
Effort from outside the penalty box by Peter Odemwingie goes wide right of the target.90:00 +1:53
Shane Long delivers the ball, Shot from just outside the box by George Thorne goes over the crossbar.90:00 +0:51
Jonas Gutierrez delivers the ball, Shot by Haris Vuckic from deep inside the penalty area misses wide to the left of the target.90:00 +0:36
Centre by Cheick Tiote, save by Ben Foster.89:29
Graham Dorrans takes the free kick.89:29 Booking
Booking Fabricio Coloccini is shown a yellow card.89:21
Fabricio Coloccini concedes a free kick for a foul on Peter Odemwingie.88:35
Shot by Chris Brunt from outside the box goes over the net.87:10
Centre by Danny Simpson. The referee blows for offside. Free kick taken by Ben Foster.86:46
Outswinging corner taken from the right by-line by Ryan Taylor.86:15
Hatem Ben Arfa sends in a cross, Shot by Cheick Tiote from 12 yards. Save made by Ben Foster.86:04
Shola Ameobi takes a shot. Blocked by Jonas Olsson.84:51
Assist on the goal came from Peter Odemwingie.84:51 Goal scored
Goal! - Paul Scharner - Newcastle 2 - 3 West Brom Paul Scharner grabs a goal from inside the area to the bottom right corner of the goal. Newcastle 2-3 West Brom.84:51
The ball is crossed by Graham Dorrans,83:54
The official flags Shane Long offside. Tim Krul takes the free kick.82:16
Corner taken right-footed by Ryan Taylor, clearance by Shane Long.81:59
Haris Vuckic produces a drilled left-footed shot from 25 yards. Ben Foster makes a save.
The ball is delivered by Jonas Gutierrez. The ball is swung over by Danny Simpson, save made by Ben Foster.80:01
Assist by Hatem Ben Arfa.80:01 Goal scored
Goal! - Demba Ba - Newcastle 2 - 2 West Brom Demba Ba finds the net with a goal from the edge of the penalty area to the top right corner of the goal. Newcastle 2-2 West Brom.79:24
Foul by Hatem Ben Arfa on Paul Scharner, free kick awarded. Ben Foster takes the free kick.79:14
Graham Dorrans crosses the ball, save by Tim Krul.78:56
Shane Long takes a shot. Save made by Tim Krul.75:01 Substitution
Substitution Youssouf Mulumbu leaves the field to be replaced by George Thorne.72:52
Effort from outside the penalty box by Chris Brunt goes wide left of the goal.72:03
Foul by Fabricio Coloccini on Shane Long, free kick awarded. The free kick is swung in right-footed by Graham Dorrans, James Perch manages to make a clearance.71:11 Substitution
Substitution Gabriel Obertan leaves the field to be replaced by Shola Ameobi.71:00
Haris Vuckic produces a left-footed shot from just outside the box that goes wide left of the target.70:12
Shot from just outside the box by Gabriel Obertan goes over the bar.70:04
The ball is sent over by Danny Simpson, clearance by Jonas Olsson.68:59
Long range effort by Cheick Tiote goes wide right of the target.68:46
Effort from 20 yards by Hatem Ben Arfa. Gareth McAuley gets a block in.67:44
Free kick taken by Fabricio Coloccini.67:44 Substitution
Substitution Jerome Thomas leaves the field to be replaced by Graham Dorrans.67:44
James Perch fouled by Shane Long, the ref awards a free kick.67:04
The ball is delivered by Ryan Taylor, Jonas Olsson manages to make a clearance.66:38
Inswinging corner taken from the left by-line by Ryan Taylor.63:59
Ryan Taylor takes a inswinging corner from the left by-line to the near post, clearance by Shane Long.63:48
Cheick Tiote has an effort at goal from 25 yards. Billy Jones gets a block in.63:29
Inswinging corner taken right-footed by Ryan Taylor from the left by-line.62:25
Corner taken right-footed by Ryan Taylor from the right by-line, clearance by Gareth McAuley.62:16
Hatem Ben Arfa crosses the ball, blocked by Nicky Shorey.61:54
Centre by Gabriel Obertan, clearance made by Chris Brunt.60:36
Ben Foster takes the free kick.60:36 Substitution
Substitution Leon Best goes off and Hatem Ben Arfa comes on.60:36
A cross is delivered by Cheick Tiote. The assistant referee signals for offside against Leon Best.60:05
Jonas Gutierrez crosses the ball, Nicky Shorey manages to make a clearance.59:48
Youssouf Mulumbu concedes a free kick for a foul on Cheick Tiote. Free kick taken by Haris Vuckic.58:18
The ball is swung over by Ryan Taylor, Ben Foster manages to make a clearance.56:51
The ball is delivered by Demba Ba, Jonas Olsson makes a clearance.56:15
The ball is sent over by Jerome Thomas, save made by Tim Krul.55:29
Free kick awarded for an unfair challenge on Jonas Gutierrez by Peter Odemwingie. Free kick taken by Ryan Taylor.55:22
Nicky Shorey produces a cross, clearance by James Perch.54:42
Chris Brunt takes the inswinging corner, Leon Best makes a clearance.54:24
Peter Odemwingie takes the chance to get an effort at goal. Ryan Taylor gets a block in.53:23
Leon Best takes a shot. Save by Ben Foster.52:53
The ball is crossed by Peter Odemwingie, Youssouf Mulumbu takes a shot. Shane Long gets a block in.52:33
Shane Long takes a shot.51:44
Shane Long challenges Cheick Tiote unfairly and gives away a free kick. James Perch takes the free kick.51:06
The assistant referee signals for offside against Demba Ba. Ben Foster takes the free kick.50:26
Chris Brunt has an effort at goal from outside the box missing to the wide left of the goal.49:51
Jonas Gutierrez fouled by Billy Jones, the ref awards a free kick. Free kick taken by Ryan Taylor.49:41
The ball is swung over by Jerome Thomas, blocked by Haris Vuckic.48:42
Effort from the edge of the penalty box by Demba Ba goes wide of the right-hand upright.48:09
Shot by Cheick Tiote. Jonas Olsson gets a block in.46:54
Fabricio Coloccini takes a shot. Blocked by Shane Long.46:35
Corner taken by Haris Vuckic.46:24
Gabriel Obertan takes a shot. Blocked by Gareth McAuley.46:15
Jonas Gutierrez sends in a cross, Gareth McAuley manages to make a clearance.45:36
The offside flag is raised against Jerome Thomas. Free kick taken by Tim Krul.45:01
The referee starts the second half.45:01 Substitution
Substitution Ryan Taylor is brought on as a substitute for Davide Santon.45:00 +2:14 Half time
Half Time The players leave the pitch at half time.45:00 +0:24
Demba Ba is ruled offside. Free kick taken by Ben Foster.45:00 +0:03
Haris Vuckic takes a shot.43:34
The assist for the goal came from Paul Scharner.43:34 Goal scored
Goal! - Gareth McAuley - Newcastle 1 - 2 West Brom Gareth McAuley finds the back of the net with a headed goal from close range. Newcastle 1-2 West Brom.43:02
Free kick awarded for an unfair challenge on Youssouf Mulumbu by Demba Ba. The ball is crossed by Chris Brunt,42:39
The ball is sent over by Chris Brunt, comfortable save by Tim Krul.40:27
Demba Ba concedes a free kick for a foul on Youssouf Mulumbu. Ben Foster takes the free kick.38:59
The ball is crossed by Davide Santon.38:45
Haris Vuckic takes a shot. Blocked by Jerome Thomas.37:23
The assistant referee signals for offside against Peter Odemwingie. Free kick taken by Tim Krul.36:32
Davide Santon challenges Jerome Thomas unfairly and gives away a free kick. Free kick taken by Billy Jones.35:28
Jonas Gutierrez crosses the ball, Headed effort from deep inside the area by Gabriel Obertan misses to the right of the target.35:11
Paul Scharner challenges Demba Ba unfairly and gives away a free kick. Haris Vuckic takes the direct free kick.33:48
Gabriel Obertan provided the assist for the goal.33:48 Goal scored
Goal! - Demba Ba - Newcastle 1 - 1 West Brom Free kick scored by Demba Ba from long range to the top right corner of the goal. Newcastle 1-1 West Brom.32:51
Jerome Thomas concedes a free kick for a foul on Gabriel Obertan.29:28
Shane Long challenges James Perch unfairly and gives away a free kick. Free kick taken by Tim Krul.28:22
The ball is sent over by Jerome Thomas, save by Tim Krul.27:29
Chris Brunt has an effort at goal. James Perch gets a block in.27:01
Centre by Jonas Gutierrez, clearance by Jonas Olsson.26:13
Corner taken left-footed by Haris Vuckic from the right by-line to the near post, Shane Long makes a clearance.26:07
The ball is delivered by Gabriel Obertan, Chris Brunt gets a block in.25:06
The ball is swung over by Chris Brunt, save by Tim Krul.23:09
Shane Long takes a shot. Save made by Tim Krul.22:45
James Perch concedes a free kick for a foul on Shane Long. Direct free kick taken by Chris Brunt.21:48
Jonas Olsson gives away a free kick for an unfair challenge on Leon Best. Cheick Tiote takes the free kick.21:12
The ball is crossed by Gabriel Obertan. Leon Best is ruled offside. Ben Foster takes the indirect free kick.19:51
Assist by Chris Brunt.19:51 Goal scored
Goal! - Peter Odemwingie - Newcastle 0 - 1 West Brom A goal is scored by Peter Odemwingie from the edge of the penalty area to the bottom left corner of the goal. Newcastle 0-1 West Brom.18:31
The assistant referee signals for offside against Peter Odemwingie. Tim Krul restarts play with the free kick.16:50
The ball is delivered by Danny Simpson, Headed effort from inside the area by Jonas Gutierrez misses to the right of the target.15:07
Chris Brunt produces a cross.13:17
Haris Vuckic takes a corner.11:32
Free kick awarded for a foul by James Perch on Shane Long. Nicky Shorey takes the free kick.11:24
The ball is delivered by Danny Simpson, Jonas Olsson makes a clearance.10:37
Foul by Davide Santon on Jerome Thomas, free kick awarded. Gareth McAuley takes the direct free kick.6:39
Effort from outside the box by Jonas Gutierrez goes wide right of the target.6:00 Substitution
Substitution Steven Reid leaves the field to be replaced by Billy Jones.1:39
Steven Reid concedes a free kick for a foul on Jonas Gutierrez. Free kick crossed by Haris Vuckic.0:00
The game kicks-off.
Live data and text provided by our data suppliers