But once they had taken the lead shortly before half-time, it seemed they might well be heading for their third victory in a row following on from wins against Wigan and Rotherham.
Gills boss Stan Ternent played on-loan Blackburn duo James McEveley and Jonathan Douglas in his starting line-up after injury had ruled out defender Barry Ashby and midfielder Alan Pouton.
They opened the scoring in the 43rd minute when Chris Hope's shot from 20-yards took a wicked deflection off the Leeds defensive wall and gave Neil Sullivan in the Leeds goal little chance of making the save.
Sullivan however prevented the Gills going in at half-time with a 2-0 lead when he pulled off a brilliant diving save to fingertip away a well struck low shot from Mamady Sidibe.
Leeds needed - and were expected - to step up their game appreciably in the second half, but there was little indication of it.
Instead, Sean Gregan was booked for dissent following a foul on Douglas and then Simon Walton was also yellow carded for talking out of turn.
In fact Gillingham should have increased their lead after 51 minutes, but Jonathon Douglas, given a great chance from close range, directed his header straight into the hands of Sullivan.
Kevin Blackwell swapped Gary Kelly for Frazer Richardson in a tactical switch in the 56th minute.
The game, however, boiled over on the hour when a heavy challenge on Michael Gray by Gills striker Darius Henderson led to unseemly clashes on the touchline in front of the Leeds dugout. Club officials also became involved in a bid to calm things down.
Referee Mark Cowburn spoke to his assistants, and then summoned over the fourth official for discussions before showing the red card to both Henderson and Gray.
That lit the fuse for Leeds who sprang into life and put the Gills under increasing pressure in the final phase of the game.
Hulse had an angled shot blocked by goalkeeper Steve Banks in the 67th minute and as Leeds moved forward menacingly, the striker on loan from West Brom, grabbed the equaliser for Leeds nine minutes from the end.
The loan striker made light of a thigh injury to get onto substitute Marlon King's cross after a mix-up at the near post between keeper Banks and central defender Ian Cox allowed him to nip in and score his fifth goal in five games for the Whites.
Former Gillingham striker King had only replaced Jermaine Wright two minutes earlier.
Leeds, who have now lost only three of their last 16 games, pressed strongly in the last few minutes and could have won it, but substitutes Brian Deane and Marlon King both missed reasonable chances.