Butler played 42 games in 1995–96, as new boss Tony Pulis led the Priestfield Stadium club to promotion out of the Third Division (fourth tier) in second place.
[3] He played 46 games in 1996–97 under Gary Megson, as the Bloomfield Road club finished one place and four points behind Crewe Alexandra in the Second Division play-off zone.
He featured 15 times in 1999–2000, before he left Vale Park for league rivals West Bromwich Albion in March 2000 for a £140,000 fee, as one of four deadline-day signings made by manager Gary Megson.
He featured in the "Battle of Bramall Lane" on 16 March 2002, replacing Lárus Sigurðsson (the only "Baggies" player to have been booked) 14 minutes before the match was abandoned.
With the club now in the Premier League, he found himself surplus to requirements at The Hawthorns and was loaned out to Bristol City,[6] for whom he subsequently signed permanently.
He played for City in the final of the Football League Trophy at the Millennium Stadium, as the "Robins" beat Carlisle United 2–0.
He played 46 games in 2003–04, including the play-off final at the Millennium Stadium, where Danny Wilson's men were beaten 1–0 by Brighton & Hove Albion.
He played 27 games under new boss Brian Tinnion in 2004–05, before leaving Ashton Gate for former club Blackpool on a free transfer in February 2005.