Gillingham remained in contention for promotion until early March, but then lost six consecutive games; the team finished the season 14th in the Fourth Division.

[6] Many of the previous season's regular starting players left the club following relegation, including goalkeeper Phil Kite, defender George Burley, and midfielders Dave Smith and Gavin Peacock.

[10] The club retained the previous season's kit design, which added a pattern of thin white lines to the team's traditional blue shirts.

[11] The team prepared for the new season with a number of friendly matches, including one against Wimbledon of the First Division; goalkeeper Jeremy Roberts played as a trialist in that game.

[12] Although he was included in the official team photograph for the season,[13] he never played a competitive game for Gillingham and there is no record of him ever signing a contract with the club.

[16] With injuries also ruling out Alan Walker, Tim O'Shea, and Brian Clarke, and further new signings not yet completed,[17] Richardson was forced to select teenagers Ricky Pearson, Peter Beadle, Ivan Haines, Russell Norris, and Steve Thompson, the last two of whom were playing their first professional matches.

[15] Peter Heritage, a forward signed from Hythe Town of the Southern League for a transfer fee of £30,000 (equivalent to £90,000 in 2023),[23] made his debut against Scunthorpe;[21] it was his first professional match at the age of nearly 29.

[27] The next two games resulted in a 1–1 draw away to Peterborough United and a 1–0 win away to Halifax Town, Steve Lovell scoring both times,[15] which took Gillingham up to 9th place.

[33][34] The winning run came to an end with a 3–3 draw at home to Colchester United on 24 November, and Gillingham then lost in the Fourth Division for the first time in nearly two months when they were defeated 1–0 by York City on 9 December.

[15] A week later, Mark O'Connor, a midfielder signed from AFC Bournemouth for £70,000 (equivalent to £220,000 in 2023), made his debut away to Exeter City;[35] the game resulted in a second consecutive defeat.

Walker scored for Gillingham with two minutes remaining, colliding with the goalpost and knocking himself unconscious in the process, but Maidstone retained their lead and won the match.

[36] Pulis made his long-delayed debut in the team's final game of 1989,[40] a 1–0 victory over Wrexham which took Gillingham up from 11th to 8th in the table, two points below the play-off places.

[51][52] By the time Gillingham lost 1–0 to Hereford United on 14 April, their sixth consecutive defeat and fourth without scoring a goal, they had fallen to 14th in the table.

As a Fourth Division team, Gillingham entered the 1989–90 FA Cup in the first round, where they were drawn to play Welling United of the Football Conference.

The initial match at Priestfield ended in a goalless draw,[61] necessitating a replay four days later at Welling's Park View Road ground.

A goal from Welling's Mark Hone in the first half was enough to give the semi-professional team victory and eliminate Gillingham from the FA Cup.

[62] It was the first time that Welling had beaten Football League opposition in the FA Cup in their history; Paul Newman of The Times described Gillingham's play in the second match as "ragged" and Welling manager Nicky Bridgen told the press "I wouldn't want to put Gillingham down but, to be honest, getting a draw on Saturday was no more difficult than drawing at somewhere like Telford in the Conference.

Gillingham lost the first leg of the two-legged tie 4–1 at Priestfield and the second 3–0 at Orient's Brisbane Road ground and were eliminated from the competition by an aggregate score of 7–1.

[67] Three weeks later, Gillingham beat Cambridge 2–0 at Priestfield;[68] goalkeeper Harvey Lim, who had recently joined the club as back-up to Hillyard after a spell playing in Sweden,[69] made his debut.

Lovell was the team's top scorer for the third consecutive season;[74] he scored 16 goals in Fourth Division matches and a total of 18 in all competitions.

Gillingham eventually achieved promotion back to the third tier of English football in 1996, ending a spell of seven seasons at the lower level.