Born in Newham, London, Charles started his career at Clapton F.C., but first came into notability at Nottingham Forest, when he became a regular alongside Roy Keane, making his debut on 7 November 1987. Due to his colour and skills, he was dubbed the Brazilian. His manager at Nottingham, Brian Clough, commented on his dribbling abilities by saying: "When Charles plays a one-two, he goes like a gazelle. It's so effortless - at first it looks as if he's not moving, yet he's 40 yards up the field." In June 1991, he made his debut for England, playing two friendlies, against New Zealand on 8 June and Malaysia on 12 June. Only a few days earlier, Charles was famously fouled by Paul Gascoigne in the 1991 FA Cup Final. This was the challenge that caused Gascoigne's cruciate ligaments to tear, forcing him out of the game for several months. On 29 March 1992, he made the squad that won the Full Members Cup against Southampton. On 29 July 1993, he made a £750,000 move to Derby County, appearing 76 times for them during a two-year spell, which included honours for PFA Team of the Year in 1993–94. On 6 January 1995, he signed with Aston Villa for a fee close to £1.4m, and assumed a regular starting role, although he was frequently injured, being out for two seasons recovering from a serious ankle injury. He appeared in 80 league matches in three and half years with the Villans, winning one League Cup. On 14 January 1999, Charles moved abroad, joining Benfica in Portugal, for a fee of £1m. He was the back-up choice after the failed bid for Oleh Luzhny. However, in Portugal, his problem with injuries remained; on 22 January, just six days after arriving, he sustained a sprain in his right hock with rupture of the joint capsule of his knee, being sidelined for two months. He finally made his debut on a 3–0 home loss against Boavista on 14 March 1999, and played in three more games, scoring one goal, before being sidelined again on late April, due to a pubalgia. Spending the entire summer recovering from injury, he was put on the transfer list by Jupp Heynckes, so he made a move to his boyhood team West Ham United on 5 October 1999 for £1.2m. During the three seasons with the Hammers, he was constantly out by injuries so he opted to end his professional career on 29 July 2002.
After the end of his playing career, Charles struggled with alcoholism. He however overcame these difficulties and has attained his UEFA A Coaching licence. In 2018, Charles was reported as being a recovering alcoholic with a business providing care to people who are experiencing depression and alcohol and drug dependency.
