Colchester made it six straight wins with Gregg Halford marking his 100th appearance for the club with a brace.
The hosts broke the deadlock on 32 minutes when Halford converted Kevin Watson's superb pass from 10 yards and Gillingham crumbled after the break.
Halford got his second with a 25-yard thunderbolt and a minute later, Jamie Cureton fired in.
Cureton bagged his brace from close range before Wayne Brown made it 5-0 by lashing home from just inside the area.
Colchester: Davison, Stockley, Brown, Chilvers, White, Halford (Garcia 71), Danns (Izzet 72), Watson, Yeates, Cureton (Duguid 74), Iwelumo.
Subs Not Used: Baldwin, Gerken.
Goals: Halford 32, 52, Cureton 54, 66, Brown 70.
Gillingham: Bullock, Clohessy, Cox, Johnson, Williams, Spiller (Harris 55), Smith (Jackman 54), Crofts, Jarvis, Flynn, Byfield.
Subs Not Used: Brown, Saunders, Rose.
Booked: Flynn, Johnson.
Ref: J Singh (Middlesex).