The Tigers surged ahead through tries from Michael Holford and in-form England Under-21 winger Tom Varndell.
But Gloucester closed the gap to 15-13 by half-time as Anthony Allen touched down and Ludovic Mercier converted.
A second Varndell try extended Leicester's lead again before the visitors answered with a Olly Morgan try, but the Tigers held on.
Gloucester head coach Dean Ryan:
"We cannot get away from the fact that the first half-hour killed us. "When we smoothed things over, we dragged ourselves back into the game. That try we missed at the start of the second half was crucial.
"We knew it would be a very physical game and we did have three or four chances but you have to put those away against Leicester."
Leicester: Vesty; Lloyd, Smith, Hipkiss, Varndell; Goode, Healey; Holford, Chuter, Morris; Cullen, Kay; Croft, Jennings, B Deacon.
Replacements: Cole for Healey (71), Moreno for Holford (46), Hamilton for Cullen (58), Johnson for Jennings (58).
Not Used: Buckland, Broadfoot, A. Tuilagi.
Gloucester: Morgan; Foster, Simpson-Daniel, Allen, Thirlby; Mercier, Richards; Collazo, M Davies, Powell; Eustace, Buxton; Balding, Hazell, Forrester.
Replacements: Fanolua for Allen (58), Thomas for Richards (70), Cornwell for Buxton (65), Boer for Balding (45).
Not Used: Parkes, Sigley, B. Davies.
Att: 16,815
Ref: T Spreadbury (England).