New signings Darren Byfield and Iwan Roberts grabbed Gillingham's goals to hand them a 2-1 victory over Leeds United at the Priestfield Stadium.
Byfield opened the scoring after just four minutes when his well struck shot took a wicked deflection off Jermaine Wright giving keeper Neil Sullivan no chance in the visitor' goal. It was the first goal Leeds had conceded at this level since Gary McAllister scored against them for Leicester in what was then the Second Division in April 1990.
Patrick Agyemang almost doubled the home side's lead midway through the half only for Sullivan to save well with his feet.
The former Wimbledon striker was allowed to continue his run from midfield and, as the Leeds defenders backed off, he let fly from 25-yards.
Player-manager Andy Hessenthaler received a big cheer from the home fans when he emerged from his place in the stands to warm up behind the goal.
He was unable to sit with the other substitutes because of a touchline ban - and he got a light-hearted welcome when he replaced the injured Nayron Nosworthy on 23 minutes.
Byfield nearly scored again ten minutes before the break when his ambitious lob from 25-yards landed on the roof of the post with Sullivan scrambling to get back.
The Whites best chance came on 40 minutes when Gillingham failed to clear a corner and the ball fell to Matthew Kilgallon, but his volley from the penalty spot was blocked by Steve Banks. Julian Joachim then nearly scored from the rebound but his header was turned around for another corner by a defender.
It was the only real chance the Leeds created in a half that was dominated by the home side.
Kilgallon was booked just minutes before for a reckless challenge on Byfield from behind, who tormented the young full-back all game.
Gillingham went into the break two-up when Roberts, on his home debut, turned Agyemang's cross into the Leeds net on the stroke of half-time.
Leeds came out in the second half with more purpose and belief, but it was not long before the home side battled them out of the game.
As Leeds pushed forward and tried to get themselves back into the game they left themselves open for a sucker-punch goal. Roberts should have doubled his tally ten minutes after the break when Danny Spiller's shot hit a wall of defenders and fell kindly for the former Norwich striker only for him to miss-hit his shot from about 6-yards out.
Joachim spent most of the match on his own upfront and left chasing long balls as a rattled Leeds defence cleared its lines.
The best chance that he could muster was on 70 minutes when he was gifted the ball following substitute Hessenthaler's mistake.
The former Coventry man was allowed to run at the home defence for the first time in the game but he blasted the ball well over the bar under pressure from Barry Ashby.
The introduction of Brian Deane and Steve Guppy on 75 minutes gave Leeds more attacking options and with just ten minutes left on the clock they pulled one back through Danny Pugh.
Guppy's cross was deflected into the path of the advancing Pugh by Banks as he tried to collect the ball and the former Manchester United player slotted the ball home from close range.
The goal provided a much needed boost for the visitors as they went in search of an equaliser and a share of the points, but were unable to get past a spirited Gillingham defence.
The Gills were good value for their win in a game marred by a 20-man fracas sparked by a scuffle between substitutes Deane and Hessenthaler.