Brighton made it three wins on the trot with a first-half goal from Bas Savage. Andrew Crofts had two good chances for Gillingham before Savage struck on 18 minutes against his former employees.
He stole the ball from Ben Chorley on the edge of the box before firing a low shot past Romain Larrieu. From then on the Brighton defence stood rock steady.
Seagulls stopper Scott Flinders fumbled Mark Bentley's header on to the bar and Michael Flynn, Chorley and Southall went close before Flynn hit the post.
Gillingham: Larrieu, Southall, Chorley, Johnson (Sancho 78), Jackman, Bentley, Crofts, Flynn, Jarvis, Mulligan, McDonald (Pugh 66).
Subs Not Used: Cox, Spiller, Collin.
Booked: Southall.
Brighton: Flinders, El-Abd, Butters, Lynch (O'Cearuill 55), Rents, Ward (Fraser 66), Hammond, Bertin, Cox, Gatting, Savage (Revell 73).
Subs Not Used: Sullivan, Elder.
Booked: Hammond, Savage, Gatting.
Goals: Savage 18.
Att: 6,609
Ref: P Joslin (Nottinghamshire).