Hereford experienced Cup success in 1990 with victory in the Albright Bitter Welsh Cup against Wrexham at Cardiff Arms Park. Colin Robinson gave United a 34th minute lead after Darren Peacock touched on a free-kick for him to crack the ball home. Wrexham levelled the scores in the 55th minute through Gary Worthington but Ian Benbow's strike restored Hereford's lead giving them a wonderful 2-1 win.

Both Colin Addison and John Sillett gave credence to the old adage that "nothing in life is ever the same going back" when they had unsuccessful second managerial spells at Edgar Street, before ex-Coventry City favourite Greg Downs took over the reigns and built a team that played attractive football. However, the team failed to make any significant impression on the league table, and suffered embarrassing FA Cup defeats to non-league Yeovil Town and Bath City before Downs was replaced by John Layton Junior. He struggled manfully at the helm of the club for a further season before the still-present Graham Turner took over at the start of the 1995/96 campaign. Turner's first season was met with a considerable amount of success with creditable runs in both the league and FA Cup. They reached the Third Round of the cup for the second time in five years, and were drawn at home to Premiership outfit Tottenham Hotspur. In front of a new capacity crowd of 8,800, Ronnie Rosenthal's goal gave the visitors the lead, before United were handed a golden opportunity to level the scores from the penalty spot. Captain, Dean Smith, sent his spot kick over both the crossbar and Meadow End to the horror of the home support, but this was to prove short lived as John Brough rose at the near post to head in the equaliser just minutes later and earn Hereford a very respectable draw. The replay at White Hart Lane saw The Bulls bow out after a 5-1 defeat, although Gareth Stoker scored a spectacular thirty-yard consolation goal, the ball hitting the underside of the crossbar and going in off 'keeper Ian Walker. Their exertions in the FA Cup sparked a fantastic league run for United and, after sitting in nineteenth place at the end of February, Hereford finished in a Play-off place (seventh) at the end of the season. Sadly, promotion dreams were shattered with a two-legged semi-final defeat to Darlington. Dean Smith gave United an early lead in the home leg at Edgar Street, only to see the Quakers hit back to win the game 2-1. The return leg at Feethams also saw Hereford lose 2-1, consigning them to another year in the Third Division. Despite this setback, fans remained optimistic for the following season. With Hereford's supporters hopeful of another assault on Third Division promotion, the 1996/97 season could not have been more different and remains the darkest year in the club's history. Severe financial problems had forced Graham Turner to part with his best players and had no money available to strengthen the squad. United had struggled throughout the campaign, but a mid-season slump of thirteen games without a win saw them sink to ninety-first place in the Football League. Bottom club, Brighton, who had seemed doomed for weeks, had undergone a tremendous revival and were threatening to pull off an amazing recovery. In the final weeks of the season, Hereford were staring down the barrel of relegation and, in their penultimate fixture, travelled to Leyton Orient knowing that a victory would put their destiny in their own hands. A highly-disputed offside goal handed Orient a 2-1 win and, with Brighton defeating Doncaster Rovers, it meant that relegation to non-league football would be settled on the last day of the season when Brighton visited Edgar Street. A win would guarantee Hereford's safety, but a draw would favour the Seagulls as, although United had a superior goal difference, the goals-scored rule was in operation at the time, with Brighton having scored just a couple more goals than The Bulls over the course of the year. In the showdown itself, Hereford started the brighter and took a deserved half-time lead thanks to Kerry Mayo's twentieth minute own goal. The hosts continued to be in the ascendancy after the break, but Brighton grabbed an equaliser against the run of play. Goalkeeper DeBont's poor kick lacked distance, and was spectacularly volleyed back towards goal. The ball cannoned back off the post and straight into the path of, the now infamous, Robbie Reinelt, who made no mistake from close range. Despite United's brave efforts, the match finished all square at 1-1, breaking Hereford hearts and condemning them to relegation from the Football League after a twenty-five year reign.

Fans' dreams of a rapid return were quashed in The Bulls' first season in the Conference, and although they finished in a creditable sixth place, it was not enough. The highlight of the season was the ironic, and perhaps inevitable, clash with Brighton in the FA Cup First Round. Two goals from Neil Grayson and a superb penalty save from Andy DeBont helped give Hereford a 2-1 win and a small amount of revenge over the club that had relegated them six months earlier.

In the 1999/2000 campaign, United savoured FA Cup success again. After defeating York City and Hartlepool United at Edgar Street both with 1-0 wins, The Bulls' were drawn at home again in the Third Round, but to Premiership outfit Leicester City. Hereford had by far the better of the play, and almost snatched a late winner when young winger Paul Parry hit the post after carrying the ball from inside his own half.