As a child Butler moved to Redcar with his family – his father was a bank manager – and attended Ryehills School. He started his professional career at Gillingham in 1991–92, who were then a Fourth Division under the management of Damien Richardson. They finished second-from-bottom in the English Football League in 1992–93 under Glenn Roeder, avoiding relegation because they finished just four points ahead of Halifax Town. They finished 16th in 1993–94 under Mike Flanagan, before dropping to 19th in 1994–95. Butler played 42 games in 1995–96, as new boss Tony Pulis led the Priestfield Stadium club to promotion out of the Third Division in second place. He made 179 appearances for the "Gills" in league and cup competitions, scoring seven goals.
Blackpool
Butler was sold to Blackpool in August 1996 for £225,000. 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. New boss Nigel Worthington played him 43 times in 1997–98, as the "Seasiders" slipped to 12th. He made 23 appearances in 1998–99, with Blackpool on the way to another mid-table finish.
He signed for Port Vale for a £115,000 fee in March 1999. He played just four games, as Brian Horton's "Valiants" managed to retain their First Division status despite a poor start to 1998–99. 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. Butler featured seven times for the "Baggies" in 1999–2000, as Megson steered the club away from the relegation zone – whilst Port Vale went down. He made 51 appearances in 2000–01, as Albion reached the play-offs, only to be defeated by Bolton Wanderers at the semi-final stage. It was in this season that he scored his only goal for the club, in a 2–1 loss to Birmingham City. He featured 23 times as the club won promotion as runners-up in 2001–02, finishing ten points behind champions Manchester City. He featured in the "Battle of Bramall Lane" on 16 March 2002, replacing Lárus Sigurðsson 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, for whom he subsequently signed permanently.
Butler joined Gary Owers' Forest Green Rovers in July 2006. During the 2006–07 season he was loaned out to Conference South side Newport County. In February 2007, Butler joined Hinckley United of the Conference North. He was released by Hinckley in November 2007, and subsequently signed for league rivals Alfreton Town.
