Later that year Gooden won promotion to the First Division with Gillingham, after they beat Wigan Athletic 3–2 in the Division Two play-off Final at the old Wembley Stadium. During the game Gooden provided a cross to Andy Thomson for him to score the winning goal. He went on to have a successful first season in the First Division with Gillingham, helping them to finish 13th in the league. He also scored in an FA Cup tie against former club Arsenal, in a 5–2 defeat away at Highbury.