Premierleague strugglers Dundee United got off to a flying start when Barry Robson headed home James Grady's cross in the third minute.
And Ian McCall's side were 3-0 up after 21 miuntes.
Mark Kerr met a punch out from Gretna keeper David Mathieson with an unstoppable first-timer from 25 yards with just seven minutes played and Mark Wilson added another from the penalty spot after home skipper Andy Aitken handled in the box.
And Wilson should have made it four when Mathieson pulled down Robson, but the keeper saved his spot-kick and Grady blazed the rebound over.
However, the third division side hit back with goals either side of half-time.
United keeper Tony Bullock palmed out a Bryan Gilfillan shot, but had no chance as Kenny Deuchar snapped up the rebound from eight yards four minutes before the break.
A minute after the restart, Mark Birch made it 3-2 from the penalty spot after amazing scenes of confusion.
Referee Charlie Richmond signalled a goal when Gavin Skelton met a cross to lash the ball past Bullock, but the referee reversed his decision and awarded the protesting Gretna players a penalty for an off-the-ball foul on Deuchar.
Scotland striker Stevie Crawford stretched Dundee's lead with a clever lob but Gretna had the final word - Skelton blasting in a 30-yard piledriver to set up a nail-biting finish.
Afterwards Tannadice boss McCall said: "I thought we fully deserved to win but all credit to Gretna, they are a club going places."
Gretna boss Rowen Alexander said: "I thought, when we fought back to 3-2 we had the game by the scruff of the neck, but we got hit by a sucker punch when they went up the pitch and scored their fourth."