After only avoiding relegation on goal difference the previous year, management duo of Jack Diamond and Stuart Robertson rang the changes for 2003-04. Captain Barry Joyce retired from playing, Darren Lockhart went to Craigroyston, defender John McGowan moved to Preston Athletic and striker Kerr Thomson was snapped up by Ormiston. A number of Edinburgh-based players were also released, with only Robbie Clark, the Lothian brothers and Jamie Yuill remaining from last year. With a squad to rebuild, the management team decided to seek out Borders talent. In came ex-Selkirk trio of goalkeeper Scott Lumsden and defenders Mark Hume and Scott Weir, while striker Gary Hastie and midfield dynamo John Kayser both joined from Gala Rovers. Galashiels youngster Sean Paliczka, who had previously been on the books of both Hibs and Raith Rovers added some flair and the team was captained by Ally Morrell, also a former Raith player who'd had experience in the East of Scotland League with Preston Athletic and Edinburgh City.

There were some changes amongst the coaching staff with Alan Notman returning from Leithen Rovers for another spell as assistant manager. He was joined by Fraser Leckie, a former Peebles and Selkirk player, who combined his coaching duties with providing cover for the goalkeeping position. Even with a capable team in place, pre-season wasn't encouraging, with Vale suffering heavy defeats to Arniston Rangers and Broxburn Athletic. Weaker, amateur opposition were beaten, but in a style that was far from impressive. Simply avoiding relegation seemed to be the only realistic target.

On a brighter note, with the aid of a grant from the SFA Youth Initiative, a Vale Under-19 side - overseen by Chris Dalgetty, Keith McCulloch, Robert Steele and Stuart McIntosh - took part in the newly formed East of Scotland Youth League alongside Berwick Rangers, Civil Service Strollers, Edinburgh City, Lothian Thistle, Preston Athletic and Spartans. The teams were also entered into the Scottish Youth Cup, with Partick Thistle paying a visit to Victoria Park in the Second Round and having to work hard for their victory.

The first team could scarcely have had a tougher start to the season, with the first two fixtures away at reigning champions Whitehill Welfare and local rivals Gala Fairydean. However, Vale surprised even themselves by taking the game to Whitehill, unluckily losing 2-1. The first of many hard luck stories awaited the following week at Netherdale though, a freak 40-yard goal and two penalties putting Gala 3-0 up at the interval. Vale hit the woodwork on four occasions and dominated the second half, with a final scoreline of 5-1 not a true reflection on the game. The following week, though, saw Vale's first home fixture where they picked up their first point of the season against Edinburgh University.

In the Scottish Qualifying Cup First Round, Vale were drawn to face Tarff Rovers. It was a repeat of the Qualifying Round fixture a year before, but Tarff had lost their manager and entire playing staff at the end of the previous season and been forced to withdraw from the South of Scotland League. There were nothing in the rules that prevented Tarff from signing experienced players from the Junior ranks on short term contracts for the game, so it was anybody's guess what quality of opposition awaited. As it turned out, any worries were unfounded as Vale progressed easily with an 11-0 scoreline. Seven players scored with Robbie Clark the star of the show, claiming four. The draw for the Second Round paired Vale with Burntisland Shipyard, the Fife men having disposed of Annan Athletic in the previous round. An early George Fairgrieve penalty gave Vale the lead, but a Tom Fairgrieve goal for Burntisland had levelled things at half time. A Jamie Yuill goal just after the restart put Vale back in front, before Gary Hastie made the tie safe. It had not been a great performance, but it meant that Vale were in the Scottish Cup First Round draw for the first time in six years. In the Qualifying Cup semi-final, a superb battling performance saw Vale only just beaten by Edinburgh City.

In the Image Printers Cup, Vale eased past Tollcross United in the First Round but a dreadful performance in a local derby against Peebles Rovers saw them crash out. Back in the league, Vale's form was inconsistent, with encouraging performances that got little reward, mixed with poor ones that deserved nothing. The management duo had brought some new faces in, with Darren Lockhart returning from Craigroyston to add some bite to a midfield that appeared lightweight and Craig Pilon coming from Abertay University to steady an uncertain-looking defence. At the halfway stage in the league campaign, the statistics did not make for pleasant reading - 11 games had yielded only one win, and Vale were rooted to the bottom of the table with only six points. The only good news was that the form of Whitehill Welfare, Lothian Thistle and Craigroyston hadn't been much better, so Vale were not out of touch with those above them.

In October , the club was saddened by the death of Eddie Sanderson, who had been involved in some capacity at Victoria Park for an incredible 69 years and had held the position of Honourary President since 1985. A minutes silence was observed before a league match against Whitehill Welfare and the players paid their own tribute on the pitch, a fantastic battling performance in driving rain bringing a 3-1 victory. In March, Willie Brunton was installed as Vale's new Honourary President.

When the draw for the Scottish Cup took place, Vale eyes were on two possible away games - Queens Park, for the chance to play at Hampden or Morton, as the best supported side at that stage in the draw. To the delight of everyone, the latter came out the hat, which meant a trip to Greenock and a tidy sum guaranteed for the kitty.

The match was originally scheduled for the 20th of December, but as the Vale players and support prepared to leave the Borders, the news came through that heavy rain in the west of Scotland had forced a postponement and the game was rescheduled for the following week. Playing the game a couple of days after Christmas proved to be a headache, as a few players already had booked up Christmas holidays. The Vale support was diminished too, with various people having other commitments. The delay had meant that Vale's name appeared as the draw for the Third Round was made though, with the winners knowing that a home tie against SPL side Partick Thistle awaited in the next round.

Morton were riding high 12 points clear at the top of the Scottish Second Division, regularly putting 5 or 6 goals past teams in their own league, and as expected they were by far the dominant side in the match. Peter Weatherston opened the scoring after quarter of an hour and right on the stroke of half time Alex Williams pounced to make it 2-0. Further goals from Chris Millar and another from Williams in the first ten minutes of the second half wrapped things up for Morton. Determined defending ensured no more goals and Vale emerged with credit from the game.

Sean Paliczka evades a tackle from a Lothian Thistle defender during a league match at Victoria Park.

Incidentally, Morton went on to lose to Partick Thistle in the next round and saw their good form collapse, with Airdrie United, trailing 14 points behind at the time of the Scottish Cup tie, winning the league 11 points ahead of Morton, who finished in 4th place.

The excitement of the Scottish Cup over, it was back to reality, and while 2004 started with an excellent victory over Threave Rovers, this was followed by two losses to Gala Fairydean - one of those in the League Cup - and defeat from relegation rivals Craigroyston in the King Cup. Mel Graham, who had started the season with Craigroyston, was signed and turned in some exceptional performances as Vale seemed to be hitting form at last. Hard fought draws over Lothian Thistle, Spartans and Annan Athletic and wins over Lothian and Preston Athletic made avoiding the drop look like a real possibility.

A below par performance against Craigroyston resulted in a draw thanks only to a last-minute penalty award, Mel Graham knocking in the rebound after his initial effort had been saved. This meant that Craigroyston were relegated for the first time in their history and that whatever Vale took from their final match would have to be equalled by Whitehill Welfare in theirs. The last game, an away fixture against an Edinburgh City side chasing Spartans for the title, was a complete disaster, Vale being well-beaten at Meadowbank Stadium. This ensured Whitehill's safety due to their superior goal difference, and left Lothian Thistle needing only two points from their last three matches to condemn Vale to First Division football for Season 2004-05. A 4-1 victory for Lothian at Threave Rovers in their very next game did just that.