The hosts were able to hold on for the victory and end a recent rotten run in the top flight during an open and entertaining game against Alan Pardew's out-of-form visitors
The hosts took the lead in the first half courtesy through Steve Sidwell after some good work by Damien Duff saw him cut the ball back to the onrushing midfielder and his deflected strike from inside the box flew into the right-hand corner.
The Magpies equalised shortly after the break through a vicious drive from outside the box by Hatem Ben Arfa, with Mark Schwarzer wrong-footed in the home goal, before Hugo Rodallega restored their advantage after nodding in from an excellent Damien Duff free kick.
Fulham boss Martin Jol made five changes to the team that lost at home to Tottenham, with Brede Hangeland returning from suspension to replace Phillipe Senderos at centre-back, while Alexander Kacaniklic, Chris Baird, Rodallega and Duff come into the side for Ashkan Dejagah, Kerim Frei, Mahamadou Diarra and Mladen Petric.
Newcastle manager Alan Pardew made just the one change for the trip, with Ben Arfa restored to the starting XI after recovering from a hamstring injury in place of Sylvain Marveaux, who dropped to the bench.
With the game played at a lively tempo and both sides showing a willingness to pour forward, it was the hosts who took the lead through Sidwell in the 18th minute, after he saw his effort deflected in off Williamson with Krul sent the wrong way.
They should have added a second moments later when Berbatov latched on to a sloppy pass from Anita before racing through one-on-one, but Krul did well to stand up as long as he could and palm the effort away.
The Bulgarian went close again on the half hour mark after a superb run and cross by Sascha Riether down the right which saw Berbatov's acrobatic effort cleared off the line by Davide Santon.
Riether then rose to nod Coloccini's powerful header from a corner off the goal-line and blocked a sweetly-struck crack on goal from Ba just before the half-time whistle, with Fulham going in at the break with a slender lead.
This prompted a response from Newcastle and they grabbed the equaliser in the 54th minute courtesy of a sensational strike from Ben Arfa from outside the area on the right which clipped the bar on its way in, with Schwarzer caught embarrassingly off guard trying to anticipate the cross.
Fulham regained the lead in the 63rd minute, though, after Rodallega buried a header at the near post, beating Coloccini in the air after Duff flung in a fabulous free kick from the right flank.
With the game opening up more and more and each side's defence looking ropey under any sort of pressure, Coloccini struck the bar with a magnificent curling effort from inside the box after a rampaging run forwards.
Nevertheless, despite both sides pushing for another goal and testing the opposition's goalkeeper with a number of efforts from range, Fulham were able to hold on to their lead and secure all three points in what represents their first league win since late October.