Lee Clark's late strike all but guaranteed Fulham a Premiership place next season.
The Geordie fired home with the right side of his foot to condemn his old team to their second defeat in a row.
However, until the dismissal of Andy Griffin, it looked to be a comfortable three points for Newcastle. The Magpies defender clattered into Luis Boa Morte to earn himself a second yellow and a mandatory red card.
It turned the game around.
Out of the blue Sylvain Legwinski fired an unstoppable shot from 25 yards in off the post to turn the game on its head.
Until then Newcastle had had the better chances. On ten minutes Olivier Bernard crossed from the left which Maik Taylor could only beat out.
Just seven minutes later Hugo Viana's tenacity in midfield let in Craig Bellamy to bring a fine save out of Taylor diving to his right.
Two minutes after that Bellamy was left raging at referee Gallagher after the speedy Newcastle forward had his penalty appeals denied.
Bellamy fell over the outstretched leg of Martin Djetou as he went round the Fulham defender in the box.
There was nothing controversial about the header from Elvis Hammond on 25 minutes.
The substitute striker headed Jon Harley's cross towards goal but somehow Shay Given scrambled across to stop the ball on the line.
It was a rare first-half attack from Fulham, and after two corners in succession Alan Shearer met the second like an express train to give Taylor no chance and put Newcastle ahead.
Hammond was an inch away from connecting with a Steed Malbranque free kick just after half time and a dipping volley from Sean Davis landed on the top of the Newcastle net.
However for all Fulham's huff and puff there seemed no way back until Griffin's red card and Legwinski's wonder strike set up Clark to delight the majority of the sell-out crowd.