The 1958-59 season began with the traditional Probables v Possibles match where a crowd of over 2,500 saw the most expensive and exciting City line-up ever assembled. Star of the game, scoring four goals, was Charlie 'Cannonball' Fleming and he then scored hat-tricks in City's opening two games against Barry Town and Worcester City. He went on to score an incredible 49 goals that season that saw City finish in 6th place and runners-up in the Southern League Cup. Despite losing local star winger Alan Skirton to Arsenal, the 1959-60 season saw City earn an unprecedented level of success. For the first ever time the Southern League Championship Shield found it's way to Bath. The icing on the cake was that the league was secured, with six games of the season left, with a 2-1 victory over local rivals Yeovil Town at Twerton Park in front of 5.496 ecstatic City supporters. This year also brought one of City's greatest ever FA Cup runs. Another victory over Yeovil in the 4th Qualifying Round began the run that then saw League sides Millwall and Notts County dumped out of the great competition. The Third Round draw saw City first out of the hat and paired with Second Division Brighton. The clash at Twerton Park ended 1-0 to the visitors thanks to a lucky goal, with 18,020 fans packed into the ground, a record attendance that still stands today.

City were unable to defend their title the following year, finishing 6th although there was again Cup success as Third Division Swindon Town were taken to a 1st Round replay. A new manager at the start of the 1961-62 season, Arthur Cole, and signings Trefor Owens from Orient and Doncaster's Ronnie Walker saw City again challenging for the top spot. Despite leading the league for several periods in the end City had to settle for the runners-up position behind the Football League headed Oxford United. On the pitch problems through injuries to vital players and off the pitch squabbles (over the state of the clubs finances, naturally) did not help City the next season and Cole resigned in November with City just seven places off the foot of the league. Although his replacement did not arrive for over four months when he did it was another big name signing. Malcolm Allison had been assistant manager at Spurs but was turning out for Southern League Romford when the call came. That season ended with City 10th but Allison brought further new recruits for the 1963-64 campaign. Ray Drinkwater (QPR), John Cartwiright (West Ham) and Len Phillips (Portsmouth) joined long-term players McFarlane, Tony Book, Carter and, of course, Fleming. Throughout the season City were genuine title contenders but had to be content with 3rd place behind winners Yeovil Town. Having exited at the first hurlde for two successive seasons City finally tasted FA Cup success again. A 4-0 replay victory over Wimbledon earned City a 3rd Round home tie with First Division Bolton. The game saw City produce some of their best football for years and a shock was on the cards when Owens put them ahead with just 17 minutes remaining. However, this lead lasted just six minutes as a Francis Lee penalty spared the Wanderers blushes. The replay, in front of a crowd of nearly 27,000 at Burden Park, was another close encounter but the league side ran out 3-0 winners.

Allison headed off to manager Plymouth Argyle within two weeks of the end of the season to be replaced by former Welsh international Ivor Powell. Less than a month into the 1964-65 season Tony Book followed Allison to Devon and with Keith Sanderson also heading to the Pilgrims the new manager was left with a reduced and aging squad. The position was worsened as the now 38-year old Fleming was reaching the end of his playing career. No longer an automatic choice he shocked the club with a transfer request in December 1964. He remained at the club until the end of the season, when he moved to Trowbridge Town as player manager, but played his last game in City colours at Hastings on 23 January 1964. In total Fleming scored 222 goals in just 311 appearances. Despite regular personnell changes City finished bottom of the league and this began a yo-yo period where they were relegated three times (1964-65, 1966-67 & 1971-72) and promoted three times (1965-66, 1968-69 & 1973-74). The one highlight of Fleming's final season was a friendly against Arsenal to celebrate the opening of the new Twerton Park floodlights (paid for by the supporters club). Facing internationals Terry Neill, Frank McLintock, Ian Ure and George Eastham, plus former City star Alan Skirton, City lost 4-2 in front of a crowd of 2,640.

(Thanks to Philip Tanner whose excellent book Charlie Fleming - An Appreciation formed the basis of this part of City's history)