Fenton joined Aston Villa as a trainee in June 1990, turning professional in February 1992. He was loaned out to West Bromwich Albion in January 1994, making his league debut against Leicester City in the same month. His loan spell at Albion was very successful, producing three goals in seven games and contributing to Albion's eventual survival in Division One, leaving many Albion fans "bitterly disappointed" when he did not sign permanently. He instead returned to Villa, making his club debut in a 0–0 Premiership draw at home to Manchester City on 22 February 1994. In March 1994, he played in Villa's League Cup winning side, playing all of the 3–1 victory against Manchester United at Wembley. Fenton made his only appearance for the England Under-21s on 15 November 1994 in a 1–0 win against Ireland U-21s at St James' Park; the team included several future full internationals, including Sol Campbell and Nicky Butt.