The gloom around Upton Park had been lifted in a week which saw Glenn Roeder's men take nine points as they beat Southampton and Chelsea at home, and then Ipswich away.
Before today the Hammers had conceded just one goal at home this season. But Jean Tigana's men enjoyed a rare away-day victory of their own thanks to a goal in each half.
Malbranque was the provider after 43 minutes when he took a corner from the left and Legwinski rose unchallenged to head home from five yards.
West Ham were then caught napping in the 64th minute and were punished again by the same duo.
Legwinski ignored protests from Paulo Di Canio that he had been fouled and instead pumped the ball forward into the West Ham box, where Malbranque crashed home the second goal.
The afternoon had started brightly enough for West Ham, who had the first good chance in the second minute. Di Canio laid the ball off for Don Hutchison to fire in a shot from 25 yards, which Edwin van der Sar blocked before gathering the loose ball.
Freddie Kanoute was a target for Fulham in the summer and he showed why with a good break in the 12th minute which might have ended with a goal.
The big striker got behind Andy Melville and on the end of a great ball over the top from Sebastian Schemmel, and suddenly he was clear inside the box.
Kanoute took the ball as far as the left angle of the six-yard box, but rolled his shot against the far post.
Another good run by Di Canio was ended when he was bundled over just a couple of yards outside the Fulham penalty area in a central position, to give the Hammers a free-kick.
But Di Canio wasted the chance when he took one step and drove the ball into the wall.
A Fulham free-kick after 24 minutes was played into the box by Malbranque and headed behind for a corner on the left. That too was taken by Malbranque right into the six-yard box and Christian Dailly made an important clearing header.
Fulham almost took the lead after 39 minutes but West Ham saved themselves with a double goalline clearance.
Collins fed Hayles, who slipped round Hislop but mis-hit a weak shot and Dailly cleared off the line with his chest after slipping over. The rebound fell to Malbranque but Foxe got back well to clear his effort off the line too.
Suddenly Fulham were in the ascendancy and they took the lead when Malbranque's corner was headed home by Legwinski.
Teenage strike sensation Jermain Defoe, who scored his first Premiership goal for West Ham shortly after coming on at Ipswich last Sunday, warmed up on the pitch throughout the half-time break, suggesting Roeder was considering an early change to try to get his team back into this game.
It looked like his chance would come after 48 minutes when Di Canio collapsed with what appeared to be an ankle injury. The Hammers skipper left the field for treatment but returned two minutes later.
Fulham won a free-kick on the left, about 30 yards from goal after 51 minutes, but Saha's left-foot curler was wide of the far post.
Di Canio made a lovely run across the edge of the box after 54 minutes and played a one-two with Hutchison, but was unlucky to just be in an offside position when he received the return pass inside the area.
The inevitable introduction of Defoe came on the hour mark, when he replaced Laurent Courtois.
The game then went beyond West Ham as Fulham punished them with that breakaway goal from Malbranque while the home team stood appealing for a foul on Di Canio.
In the end, it could have been worse for West Ham. Hislop made a good block to deny Malbranque again after 75 minutes, and Foxe was lucky to escape conceding a penalty after he appeared to bundle over Hayles eight minutes later.
Foxe and Hislop then combined to keep out another Hayles effort with two minutes remaining, and there was time for substitute Bjarne Goldbaek to also be denied by a good Hislop save.
West Ham almost pulled one back in injury time when Di Canio's corner was met by Dailly's powerful header, but van der Sar saved. Michael Carrick followed up but his shot was blocked on the line by Rufus Brevett.
It would have been nothing more than a consolation, and the final whistle followed soon after to confirm a useful and deserved away win for Fulham.