The two most notable features of City's first season back in the Southern League, now named the Beazer Homes League, was the number of managers used and the arrival of a striker who would become the clubs greatest goalscorer since Charlie Fleming. Harold Jarman was initially handed the task of getting City back into the Conference but he only lasted until October. Following a short caretaker spell under Colin Tavener larger than life ex-Trowbridge Town boss Les Alderman took over. Despite a number of big wins City never looked like challenging for the title and as they began nervously looking over their shoulders at the relegation places Alderman was replaced by Geoff Evans. Going into the final week of the season City were still in relegation danger before two victories secured a ninth place finish. A scorer in both these games was Paul Randall. The former Bristol Rovers and Stoke City forward arrived in April and would go on to score 112 goals in just 210 appearances during the next five seasons. In the FA Cup City reached the 2nd Round before surrendering a 2-0 lead to exit 3-2 against Welling United and miss out on a meeting with Blackburn Rovers.

Under another new manager, George Rooney, the 1989-90 season began in less than auspicious circumstances with a 2-1 defeat at Cambridge City but just two further defeats up to the end of the year left City at the heart of a three-way battle, with Dartford and Dover Athletic, for the title. City started 1990 with an incredible 14 successive league wins as Randall (51 goals), John Freegard (36) and Gary Smart (25) formed an attacking force that was proving unstoppable. This run saw off the challenge of Dartford but City could still not shake off Dover. A defeat at Worcester handed the initative to the Kent side and despite four wins and a draw in the remaining five games, which left City with 98 points, they had to settle for second place. However, with Dover's Crabble Athletic ground failing to meet Conference standard City were handed a lifeline. After an unsuccessful appeal to the FA the White's were denied promotion and City were back into the Conference. Incredibly success in knockout competitions saw City play 27 cup games that season. Second Division Fulham came within twenty minutes of becoming City's first league scalp since 1965 when they trailed 2-0 at Twerton Park in a 1st Round meeting. However, two goals from Clive Walker saved their blushes and despite City taking the lead in the replay the Cottagers won 2-1. The FA Trophy also provided a memorable run. Wins over Witney, Ashford, Tow Law and Woking carried City to a quarter final tie with Conference side Stafford Rangers. An even match looked to be heading for a replay before two late goals saw the visitors through and deny City a semi-final place.

Back in the top flight of non-league football City struggled to cope with the higher standard and for much of the 1990-91 season an immediate return to the Southern League looked a real possibilty. Rooney was sacked in March 1991 to be replaced by long serving player Tony Ricketts. Just three defeats in the final 14 games under Ricketts secured their Conference place. As before once they had found their feet a series of mid-table finishes followed and it was again the FA Cup that provided success. The 1992-93 season witnessed an eight game run that began with a 4-0 win at Glastonbury and ended in a 3-0 2nd Round replay defeat at 2nd Division Northampton Town. Inbetween Third Division title hopefuls Cardiff City were beaten at Ninian Park by three goals to two. Next season City went one better to reach the Third Round. In front of the Sky cameras City beat Hereford United 2-1 to earn a trip to 1st Division Stoke City. A 0-0 draw at the Victoria Ground earned City a deserved replay before they bowed out of the cup with a 4-1 defeat. City began the 1994-95 competition in the 1st Round where they drew tenants Bristol Rovers. The Pirates showed no respect to their landlords though running out 5-0 winners.

When Rovers left Twerton Park 18 months later City were faced with a massive drop in income. The money earned from the previous ten years had been spent and the only way to prevent financial disaster was to cut the playing budget. This prompted Ricketts to resign and he was replaced by former player Steve Millard. Forced to rebuild almost from scratch City looked destined to relegation from almost the first kick of the 1996-97 season. Rock bottom going into February they finally began to show signs that an unlikely escape could be possible. Seven wins and three draws from the next twelve games meant they went into the final match of the season still in touch. When they trailed Northwich Victoria 2-0 it looked as if all hope was gone, however an incredible second half comeback saw them win the game 3-2. It was all in vain though as Halifax Town's 4-2 win at Stevenage saved the Yorkshire side and sent City down.