Prior to the start of the 1995–96 season there was a lot of talk about the possibility of building a new stadium to bring Stoke up to the requirements of the Taylor Report. On the pitch Stoke enjoyed their most successful season for quite a long time as they mounted a push for promotion to the Premiership and made the end-of-season play-offs against Leicester City. Unfortunately for Stoke Leicester scored the only goal in the two-legged tie and they went on to be promoted.
There were few transactions taking place in the summer of 1995 with the main talk being about a change of home. The Taylor Report had come to the conclusion that all football stadia in England should be all-seater and the best option for Stoke would be to build a new stadium rather than convert the Victoria Ground. The season began slowly with one win picked up in the first eight matches and with Icelandic midfielder Toddy Orlygsson leaving for Oldham Athletic after a contract dispute. But wins over Midlands rivals West Bromwich Albion and Wolverhampton Wanderers kick started Stoke's season and after a 5–0 win at home against Luton Town, City went on a run of six wins in seven and took the team into the play-off zone. In November Stoke completed a master-stroke signing swapping the poor-scoring Keith Scott for Mike Sheron at Norwich City. He formed a great partnership with Simon Sturridge and the pair scored 29 goals between them this season.
Fielding a settled side, Stoke continued to remain in the hunt for promotion and after a 2–0 win at home to rivals Barnsley at the start of March Stoke put distance between themselves and 7th. But on transfer deadline day Paul Peschisolido was controversially sold back to Birmingham City with Macari claiming not to have been aware of any deal. Attention was diverted by Sheron's club record run of seven goals in seven games as five wins out the last seven cemented Stoke place in the play-offs. By this time it was agreed and ratified that in two years Stoke would be moving to a new purpose-built all-seater stadium. Stoke's opponents in the play-offs were Martin O'Neill's Leicester City whom Stoke had already beaten twice in the league. The first leg at Filbert Street ended 0–0. In the second leg, Stoke produced a poor performance and Leicester scored the only goal, Garry Parker's left-foot volley ending Stoke's hopes of promotion.
Stoke drew Chelsea in the second round and after a 0–0 draw at home Stoke produced a brilliant performance away at Stamford Bridge and came away with a memorable 1–0 victory thanks to a 75th-minute goal from Paul Peschisolido. Alas Stoke couldn't match another Premiership side, Newcastle United, who eased to a 4–0 win.