While Howard Wilkinson was heavily backed with funds by new owners Caspian, there were rumours of discord between him and recently appointed chairman Bill Fotherby. The club made a respectable enough start, earning 7 points from their first 4 games, but a 4-0 home defeat to Manchester United in September prompted Wilkinson's dismissal after eight years as manager. With assistant manager Mike Hennigan and first-team coaches Dick Bate and Eddie Gray also being dismissed alongside Wilkinson (though Gray would subsequently be reinstated), it became clear that Fotherby wanted a clean slate for the club after the massive disappointment of the previous season.
Wilkinson's successor was George Graham, back in football after a one-year ban arising from the "bung" scandal that had cost him his job as Arsenal manager back in February 1995. Graham was unable to improve the club's dismal goalscoring record (they finished with just 28 goals, the lowest number in Premier League history until that point; it would not be until the 2002-03 season when another club, namely Sunderland, scored fewer goals) but he managed to steer them well clear of relegation in a respectable 11th place, with a total of a staggering 20 league clean sheets all season.
Record signing Lee Sharpe failed to live up to expectations and, by the end of the season, it was rumoured that he would be on his way out of the club, while Tony Yeboah made just six appearances after recovering from a long-term injury; he, too, appeared to be heading for the Elland Road exit door. Full-back Tony Dorigo's future at the club was also thrown into doubt by the emergence of Ian Harte, while midfielder Carlton Palmer's days at Leeds were also looking numbered.