Andy Barcham pulled one back for Gillingham but Jermaine Beckford hit the fourth 11 minutes from time to lift the hosts to the top of the table.
They leapfrog two points above Charlton who were held to a late 2-2 draw at Norwich.
YEP chief football writer Phil Hay takes a close look at how Leeds United's players performed against
Jason Crowe: Crowe's area of the field was where
Patrick Kisnorbo: Though his partnership with Bromby could not be described as watertight, Kisnorbo was immense individually, commanding in the air and alert to everything Gillingham attempted...9/10
Leigh Bromby: Caught off guard when
Andrew Hughes: Quietly efficient in the left-back role and won his head-to-head battle with Dennis Oli. Looking more assured by the game and has grown in an unfamiliar position...7/10
Robert Snodgrass: Instrumental in two goals, teeing up Johnson's first and helping to play in Howson, but the right side of United's team looked increasingly exposed by the time he was substituted...6/10
Jonathan Howson: In command for much of the game and although Gillingham began to hustle him after the break, he kept on top of that scrap and claimed his goal with a ruthless finish...8/10
Michael Doyle: Unlucky to see a shot crash off the crossbar, capping a day when he was forced to play second fiddle. Toiled for a period in the second half but Kilkenny's arrival helped...7/10
Bradley Johnson: Johnson's ability in the air is one of his biggest assets and his bullet header made the most of it. His second strike was also well taken, under pressure from Fuller...8/10
Luciano Becchio: His movement and hold-up play was a big factor in United's dominance and it's difficult not to feel that Leeds might miss Becchio as much as they would Beckford...7/10
Jermaine Beckford: If every effort of his which has hit the woodwork this season had found the net instead, he would be well into double figures. On the spot to round off the scoring...7/10
Lubomir Michalik (for Snodgrass, 67)...6/10
Neil Kilkenny (for Crowe, 67)...6/10
Mike Grella (for Becchio, 80)...5/10
Not used: Casper Ankergren, David Prutton, Andy Robinson, Enoch Showunmi.
Gillingham: Royce, Fuller, Bentley, Gowling, Palmer, Oli (Erskine 81), Maher (Payne 83), Jackman, Barcham, Weston (Rooney 88),
Subs (not used): Nutter, Richards, Miller, Julian.