The sky blues from the south outplayed the Austrian champions in the second-leg of their qualifying tie to overturn a 2-1 deficit and seal a dream place in the group stages of Europe's top competition.
Markus Rosenberg, who recently returned to his home-town club after a ten-year spell in the German, Dutch and Spanish leagues, was instrumental in securing the win.
The 31-year-old striker opened the scoring in the 11th minute from the penalty spot after Magnus Eriksson was hauled down in the box at the end of a scintillating move. Pulses raced in the crowd of 21,000 at the Swedbank Stadium but Rosenberg showed no sign of nerves as he coolly placed his spot-kick high in the centre of the net.
Just eight minutes later, Eriksson sent the fans into raptures when he caught a seemingly innocuous dropping ball on the volley and sent it arcing improbably over a helpless Gulacsi in the Salzburg goal.
Malmö were rampant and thoroughly deserved to advance, but nerves remained fraught until Rosenberg scored his second of the night in the 84th minute. An inviting ball into the box made the goal seem inevitable but Rosenberg turned it into a delicious slow-motion moment; when it seemed easier to prod the ball home with his left, he instead waited for the goalkeeper and a defender to commit to a tackle before jinking inside to unfreeze Malmö hearts and tap with his right and spark frenzied scenes in the stands.
Rosenberg said the win was "too big to grasp", while Eriksson described the night as the best of his life. Many in football-mad Malmö shared that feeling, as the club that reached the final of the European Cup in 1979 makes a welcome, and financially rewarding, return to the continent's top stage.