With a place in the new formed Conference South on offer for the top 13 finishers the 2003-04 season was a vital one for the newly supporter-owned City. Just three wins in their opening nine league games was not a great start and when an embarrassing 7-0 defeat at Worcester City in September heralded a run of eleven matches without a win, along with a shocking, and costly, FA Cup exit at the hands of lower league Thame United, City found themselves rock-bottom of the table. This run cost Alan Pridham his job in November and two weeks later vastly experienced former Bristol City and Sunderland player Gary Owers was named as his replacement in a player/manager role. He got off to a perfect start at Twerton Park, scoring after just 11 minutes into his debut to help City to a 2-1 FA Trophy win over Gloucester City. There wasn’t an immediate upturn in their league hopes though, as only at the fourth time of asking did Owers celebrate a league victory, Tiverton Town beaten 2-1 at Twerton Park on Boxing Day. However, the arrival of two players, who would both go on to become modern day City legends, in January 2004 began the recovery. Goalkeeper Paul Evans was signed following his release from Rusden & Diamonds the previous month and striker Scott Partridge arrived from fellow Southern League side Weymouth. It took Partridge five games to get off the mark but he was then unstoppable, scoring 18 times in the next 20 games, including three hat-tricks. The real turning point took place in Kent on February 7 when City overcame a 3-0 half-time deficit to draw 3-3 against Dover Athletic. Two weeks later a 3-0 win at Moor Green signalled a first away win for over a year and four wins in their final four matches of the season was enough to lift City from the foot of the table to 16th place, which earned them a spot in the end of season play-offs for a place in the Conference South. When Partridge put them in front against Dorchester Town in the semi-final at Twerton Park it looked as if this recovery would continue, but the Magpies had other ideas and bounced back to run out 4-2 winners and condemn City to relegation in all but name.

The 2004-05 season turned out to be another one of league heartbreak. The introduction of play-offs meant even with City struggling in the bottom half of the table going into February 2005 the season was still alive and an unbeaten 12 game run meant going into the final match of the season a play-off place was still achievable. However, despite beating Aylesbury United 2-0, results elsewhere saw them miss out to Bedford Town on goal difference. There was some compensation that season in the club’s best FA Cup run since 1993-94. Wins over Bridport, Havant & Waterlooville, Brokenhurst – where a Partridge treble earned him the player of the round award and a VIP trip to Wembley – and Leatherhead, saw City reach the 1st round proper where they were paired with Conference leaders Barnet. They produced one of the shock results of the round, two Partridge goals firing them to a 2-1 win and a 2nd round trip to Peterborough. They couldn’t repeat these heroics – going down by two goals to nil – but it was still a memorable campaign.

Just as it appeared City had found some stability both on and off the pitch – although debts were still increasing as the future of Twerton Park remained unclear – they were to receive a shock when Owers quit the club to take over the managerial reigns at Forest Green Rovers. This meant new chairman Geoff Todd’s first task as was to appoint a new manager and this turned out to be former Merthyr Tydfil boss John Relish. After opening the 2005-06 season with three wins, results were mixed and City were just on the fringes of the play-off positions midway through the season. An unbeaten run of 15 matches from the start of 2006 carried them to the top of the table and, even though they couldn’t quite hold off Salisbury City, a final day win at King’s Lynn ensured the runners-up spot and, more importantly, a play-off place. Disappointment was to follow again as Bedford beat them 1-0 at Twerton Park but this was forgotten the following season as City secured their first Southern League championship for 29 years. After an up and down first half to the season a 5-0 win over Cheshunt in January 2007 lifted them to the top of the table, from which they would never slip. The title was secured in the penultimate match of the season at Yate Town to spark joyous celebrations and, finally, a place in the Conference South.

With just minor changes to the squad City adapted immediately to the higher level and for three-quarters of the season they occupied a play-off place. However, a dip in form in the closing months saw them finish in 8th place, missing out on the play-offs, and a possible second successive promotion, on the final day of the season.