John Gorman, who was Glenn Hoddle's assistant as England manager, was appointed to help Andy Hessenthaler as the side started the 2004/2005 season poorly, but as they continued to struggle at the wrong end of the table Hessenthaler resigned as manager in late November. Somewhat uniquely he continued to be employed as a player. Gorman succeeded Hessenthaler in a caretaker capacity before leaving the club to take the manager's job at Wycombe Wanderers. Gillingham then appointed former Burnley boss Stan Ternent as manager, but despite a late run of positive results, he couldn't prevent the Gills' relegation to League One on the last day of the season. In a cruel reversal of the previous season's fortunes, Crewe Alexandra, the club above them, survived by just one goal.

The 2005/06 season started with Neale Cooper being appointed as the new manager and several new players being signed. Performances, however, were heavily disappointing, despite a 3-2 win over Premier league side Portsmouth in the Carling Cup, and shortly after defeat in the 1st round of the FA Cup by UniBond Premier side Burscough, Neale Cooper left the club. He was replaced, initially in a caretaker capacity, by Ronnie Jepson, who had been assistant to both Ternent and Cooper. Although demotion fears dogged the team for much of the years, The Gills recovered to end the campaign in 14th position, by which time Paul Scally had given Jepson a two year contract.