Celtic fell to one of their most embarrassing defeats ever in manager Gordon Strachan's first game in charge.
Juraj Halenar's tap-in gave Artmedia a 1-0 half-time lead in the Champions League second qualifying round tie.
But Blazej Vascak doubled the lead from close range after the break and Halenar added a thunderous volleyed third.
Martin Mikulic scored a fourth on the turn from the edge of the box and Halenar got his hat-trick with a low drive in injury time.
The result leaves Celtic in serious danger of elimination from Europe altogether, as the losers from second qualifying round games do not go into the Uefa Cup.
It was the visitors who first threatened eight minutes in when John Hartson headed an Alan Thompson free kick narrowly wide, though the offside flag would have ruled the effort out in any case.
Celtic were dealt a blow early on when Chris Sutton was forced out of the game with a suspected fractured cheekbone after a freak collision with Neil Lennon.
The home side seemed to take heart from that and put together a period of sustained pressure.
The closest they came to a goal was an opportunist effort from Vascak who tried to catch Marshall out at his near post, but the keeper was alert enough to turn it round the post.
Then Helenar broke free but sliced his shot wide.
The home side's keeper Juraj Cobej was called into action for the first time after 28 minutes to comfortably hold an Aiden McGeady free kick and a minute later he punched away a fierce Paul Telfer drive.
Artmedia were still enjoying the better possession and Marshall was forced into a good save to deny Daniel Tchur low to his right.
Halenar (left) celebrates his first goal
But Marshall was helpless to stop Artmedia taking the lead two minutes before half time.
Jan Kozak's pass split the Celtic defence wide open and as Branislav Obzera raced through on goal, he took Marshall and the chasing defenders out of the game by squaring the ball to Halenar who fired into an empty net.
In first half injury time Marshall got down well to keep out a goal-bound Jan Durica header.
Celtic fell further behind to a goal of superb quality. Kozak knocked a perfectly-weighted pass to Halenar, whose first-time cross was slammed into the net by Vascak.
Shaun Maloney came on for Maciej Zurawski and almost made an immediate impact when he found himself with just Cobej to beat, but the keeper blocked his shot.
Moments later he squared the ball only for McGeady to knock it over the unguarded goal.
Incredibly Artmedia added two more goals within the space of three minutes. First Halenar scored a terrific volley from a rather fortuitously awarded corner, when Marshall appeared to have kept the ball in.
Then sub Mikulic swivelled on the edge of the box to fire past Marshall.
Maloney curled a late free kick just wide with a few minutes left, leaving Celtic with a massive task in six days' time.
Artmedia Petrzalka: Cobej, Debnar, Durica, Kotula, Vascak (Mikulic 72), Obzera, Tchur, Halenar, Borbely, Fodrek, Kozak.
Subs Not Used: Kollar, Stano, Hellebrand, Gomez, Gajdos, Burak.
Goals: Halenar 43, Vascak 57, Halenar 75, Mikulic 78, Halenar 90.
Celtic: Marshall, Telfer, Varga, Balde, Camara, Zurawski (Maloney 60), Lennon, Petrov, Thompson (Aliadiere 66), Hartson, Sutton (McGeady 17).
Subs Not Used: Boruc, McManus, Wallace, Beattie.
Booked: Petrov, Balde.
Ref: Selcuk Dereli (Turkey)