Danny Spiller's first senior goal denied Watford their first win of the season in an entertaining game at Vicarage Road.
The Hornets started the game at the bottom of Division One following three successive defeats without finding the net, while their opponents had hit the target just oe in their opening four league fixtures.
The home side started brightly, with Neal Ardley picking out Heidar Helguson from the left but his header flew wide of the left-hand post.
Helguson did not have to wait long to break the deadlock, however, as Lee Cook fed Paul Robinson, and his pin-point cross was met with a thumping 15-yard header from the Iceland international.
The Hornets struggled to settle following their electric start, allowing Gillingham to hit back with long-range shots from Chris Hope and Nicky Southall.
But they soon found their feet again, with Helguson unlucky not to grab his second goal of the game.
His sweetly-struck shot from a Neil Cox free-kick fizzed inches past the upright in the 28th minute.
The game burst into life seven minutes into the second half.
A long punt upfield from Ian Cox eventually found Paul Shaw, and the Gills forward, who scored 12 goals last season, opened his account for the new campaign, coolly slotting the ball past Alec Chamberlain.
Andy Hessenthaler's side remained on level terms for just two minutes, however, as Cook's cross on the run was neatly converted by Danny Webber.
Goals, which had been so hard to come by for both sides, were now coming all too easily, with the visitors levelling matters for a second time just after the hour.
Cox found John Hills with a raking pass, and he burst forward before crossing for midfielder Spiller to head home.
Both teams pushed forward in search of a winning goal, with Watford substitute Scott Fitzgerald coming closest with a rising shot.
Ardley was shown a straight red card at the death after bringing down Sidibe with the big striker through on goal, but they held on.
Watford: Chamberlain, Ardley, Cox, Gayle, Robinson, Dyer,
Mahon, Hyde, Cook, Webber, Helguson.
Subs: Dyche, Lee, McNamee,
Hand, Fitzgerald.
Gillingham: Brown, Ashby, Hope, Cox, Southall, Spiller, Shaw,
Perpetuini, Hills, King, Sidibe.
Subs: Bartram, Hessenthaler,
Leon Johnson, Rose, Crofts.
Referee: M Warren (W Midlands)