The 1995–96 season was Port Vale's eighty-fourth season of football in the Football League, and second successive season in the First Division. Despite a poor start to the season, John Rudge led his side to a twelfth place finish. The league highlights were two derby wins over Stoke City, had these results gone the other way then Stoke would have won automatic promotion to the Premier League. Vale's excellent mid-season form also raised hopes of a promotion campaign, but they faded away at the final stages. In the FA Cup, Vale achieved a celebrated upset by knocking out holders Everton with a 2–1 win at Vale Park. They were then eliminated at the Fifth Round, after taking Leeds United to a replay. They reached the final of the Anglo-Italian Cup, where they were defeated 5–2 by Genoa. These successes did not translate to the League Cup, where Vale exited at the First Round. Key new signings were Lee Mills and Player of the Year Jon McCarthy, though it was established star Tony Naylor who was the club's top-scorer.
The season started terribly, as Vale won just one of their opening ten league games, failing to find the net in half of these fixtures. However the one win during this time was against the most important of opponents, rivalsStoke City at the Victoria Ground. The derby took place on 27 August, and a crowd of 14,283 witnessed Ian Bogie score the only goal of the game. Their win over Huddersfield Town at the Alfred McAlpine Stadium at the start of the October was also followed by a sequence of eight games without a win, leaving the club staring relegation in the face. In November, Canadian international defender Randy Samuel signed after impressing on trial, but soon was sidelined with a serious knee injury. Meanwhile John Jeffers left the club for Stockport County. The Vale turned a corner in December, and would remain one of the division's form sides until April, losing just two league games in a run of nineteen games, picking up eleven wins. One of these wins was against Stoke, who left Burslem on 12 March with a 1–0 defeat. To Stoke, Bogie lived up to his name, as he scored his second league goal of the campaign in front of a Vale Park crowd of 16,737. Vale were facing the prospect of a promotion battle to reach the top-flight of English football, the Premier League, for the first time in their history. However just two wins came in the final ten games, leaving Vale to settle for a top-half finish.
They finished in twelfth place with sixty points, eleven points shy of Charlton Athletic in the play-off zone, and eight points clear of Millwall in the relegation zone. Tony Naylor was top-scorer with twelve goals in all competitions, closely followed by Martin Foyle, Andy Porter, and Jon McCarthy.
In the FA Cup, Vale faced a difficult tie against Crystal Palace. After a goalless draw at Selhurst Park, the Vale advanced with a 4–3 win thanks to a brace from Ray Walker. They then faced the Premier League cup-holdersEverton at Goodison Park. Foyle equalized after the "Toffees" scored the opener, and Ian Bogie saved the day with a deflected goal in injury time after Everton had again taken the lead through Duncan Ferguson. This goal saved the blushes of Foyle, who missed a sitter from six yards earlier in the game, and Paul Musselwhite, who gifted Ferguson his goal when he spilled Anders Limpar's cross. Back at Vale Park, the "Valiants" added another scalp to their collection with goals from Bogie and McCarthy to win the match 2–1. The club also took in their highest ever gate receipt total, as the game saw Vale bank £170,349. They then faced another top side away in the Fifth Round, Leeds United at Elland Road. A goalless draw raised hopes of another cup upset, and hopes turned to expectations as Naylor put Vale ahead in the replay. However two goals from Gary McAllister saved United's blushes, dumping Vale out of the cup. For their efforts, John Rudge's side were handed the FA's Giantkillers award for the season.