The sure boot of Melbourne captain Cameron Smith condemned Leeds to a second consecutive World Club Challenge defeat in a tough and uncompromising clash at Elland Road, which the Storm eventually won 18-10.
In a defence-dominated match of precious few chances, Leeds teenager Kallum Watkins had two tries disallowed as the Rhinos cast aside their unimpressive Super League form to push the Australian champions all the way in front of a crowd of 27,697.
Leeds battled manfully after losing its inspirational captain Kevin Sinfield with a dead leg after half an hour and only went behind for the first time just short of the hour.
A thrilling 80-metre try from Danny McGuire promised much but a last-minute try from winger Anthony Quinn, who was in the Melbourne side that lost 11-4 to the Yorkshiremen two years ago, finally ended Leeds' resistance and earned the Australians revenge for their 2008 defeat.
It was bruising and brutal, befitting of any Anglo-Australian clash, and tempers flared towards the end of the first half after Leeds' Australian hooker Danny Buderus was dumped on his head by substitute Hep Cahill after passing the ball, and punches were thrown a second time near the end.
Melbourne's spoiling tactics at the play-the-ball infuriated the crowd and prompted referee Richard Silverwood to issue a warning to Smith but Storm would not be deflected from their goal.
The damp, sticky conditions clearly did not suit rangy centre Greg Inglis, the Golden Boot winner who was largely anonymous, while Leeds' effective kick-chase nullified the counter-attacking threat of Billy Slater, the best broken-field runner in the game.
Neither side would budge in defence, although Leeds had the better of a try-less first half.
Full-back Brent Webb got over the line in the opening moments without being able to ground the ball while Watkins, a replacement for prolific winger Scott Donald, was denied when slow-motion replays revealed he lost control of the ball and England captain Jamie Peacock was hauled down just inches of the line.
Melbourne's best chance came deep into first-half stoppage time when hooker Ryan Hinchcliffe picked up a loose ball to cross the line but video referee Phil Bentham ruled out the try after spotting a knock-on in the build-up from Slater.
Smith, playing out of position at scrum half, cancelled out penalty goals from Sinfield and Rob Burrow to leave the sides locked at 4-4 at the break.
The initial breakthough came seven minutes into the second half when Smith's kick on the last tackle rebounded off the leg of Leeds centre Brett Delaney and McGuire sped 80 metres untouched after scooping up the loose ball.
The time it took for video referee Phil Bentham to determine that McGuire was not offside merely added to the growing tension and the positive outcome raised home expectations to new levels.
Burrow's successful conversion opened up a six-point lead but it was all square just three minutes later when the Rhinos were caught napping by a quickly-taken tap penalty.
Fast hands from Brett Finch, Adam Blair and Dane Nielson worked the ball out to the wing where Luke MacDougall finished strongly for the try and Smith emulated Burrow by landing the touchline conversion.
Smith then put his side in front for the first time just short of the hour after Leeds centre Keith Senior was penalised for dissent with his side in possession and, after Watkins had been denied a second time, Quinn grabbed a second try just before the end to put the issue beyond doubt.
Fittingly, Smith landed another superb goal to maintain his 100 percent record and lifted the man-of-the-match award.