The fans were kept engrossed throughout as the game had just about everything, and Gretna probably did just enough to deserve their win.
The home side came close to opening the deadlock in the eighth minute when Colin McMenamin glanced a Fabian Yantorno free-kick just over.
Within seconds United raced forward and Willo Flood crossed to the back post where Evan Horwood slipped, allowing Noel Hunt to stab the ball back across the face of goal for Prince Bauben to side-foot home the opener.
Five minutes later Chris Innes fired in a terrific 25-yard shot that produced a fine save from Grzegorz Szamotulski.
From the corner that ensued, Yantorno's kick found its way to David Cowan and he stole in to shoot past the helpless keeper.
Szamotulski came to United's rescue midway through the first half, brilliantly pushing away a stunning Yantorno free-kick that looked to be on its way into the net.
United should have gone in front three minutes later, but Hunt shot wide after being sent clean through by Flood and Barry Robson.
In the 36th minute Fir Park erupted as the Gretna fans celebrated their side's second goal. Cowan's cross from the right was headed back across goal by McMenamin, and Cowan followed up to head home his second goal of the game.
Gretna keeper Greg Fleming pushed away a Robson free-kick at the start of the second half and, moments later, Darren Dods saw his header from a third free-kick go just wide.
In the 57th minute Robson was again denied by a fine Fleming save from another free-kick.
Gretna almost grabbed a breakaway goal when Yantorno guided a great ball onto the head of Aurelien Collin, but his effort crashed off the face of the bar and, although McMenamin picked up the rebound, he shot weakly at the keeper.
United drew level in the 65th minute when Lee Wilkie was given time and space to head home a Robson corner, despite the appeals of the Gretna players, who were looking for handball.
Gretna grabbed the winner in the 86th minute when substitute Allan Jenkins headed home, after a brilliant cross from Horwood had taken out the United defence.
With time running out United threw everything at Gretna but could not find their way past the stubborn Black and Whites defence.
Fleming made a brilliant double save to deny Robson, and then Hunt, before Cowan headed an effort off the line to preserve Gretna's lead.