Fleming played for the Dublin-based youth club Belvedere, and was signed by Brian Kerr for St. Patrick's Athletic in the summer of 1987. He was one of a number of young players signed as Kerr sought to build a squad that could challenge for honours. In his first season, he ousted former international player Eamonn Gregg from the first eleven and quickly established himself as one of the most exciting talents in the league. He won four caps for the Republic of Ireland under-21 side and was the only home based player when playing for the Republic of Ireland under-23 side against Northern Ireland in 1989. He was transferred to Swindon Town in March 1989 but returned in the summer having not played for the first team. After finishing second in his first season, Fleming won the league with St. Pat's in 1989–90 season and earned the moniker Black Pearl of Inchicore Mark II. In November 1990 he was awarded the FAI's Under-21 Player of the Year award. He also played in the European Cup and UEFA Cup while at Richmond Park.
Middlesbrough
Despite signing for Shamrock Rovers Fleming moved to England in the summer of 1991 to join Middlesbrough on a £50,000 transfer. He helped Lennie Lawrence's side gain promotion to the newly formed Premier League in his first season. After being relegated, it took 'Boro' until 1995 to be promoted again, this time with Bryan Robson in charge they won the first division title. As Middlesbrough alternated between the Premier League and First division, Fleming remained a constant in the side and as part of Robson's squad he was on the losing side in the League Cup finals in 1997 and 1998 and the FA Cup Final in 1997. On 5 August 2001, Middlesbrough played Athletic Bilbao in a testimonial match for Fleming. He played 266 league games for Middlesbrough before finally moving on.
After Middlesbrough
Fleming went on loan to Birmingham City in November 2001, playing six games for them. He then completed a move to Crystal Palace at the end of December 2001, for a fee believed to be "in the region of £100,000". Unfortunately for Fleming injuries would curtail his involvement at Palace, although Ian Dowie was impressed enough to make him club captain. After two and half seasons at Crystal palace, Fleming moved back to North East England in July 2004 to sign for Darlington on a one-year contract. He remained at the club until the end of the 2004–05 season. Fleming briefly joined Shelbourne in the League of Ireland, and played in the Champions League qualifiers, but at the end of the Irish 2005 season, Fleming officially retired.
Fleming later worked as a pundit on Setanta Sports for a period during 2006 and was linked with the position of assistant manager to Pat Fenlon at Derry City in the League of Ireland. His playing career has continued at an amateur level, with Fleming appearing regularly in the 2006–07 season for Northern League side Billingham Synthonia as a central defender. Curtis is a valued supporter of the charity Show Racism the Red Card and spoke with passion and humour about his experiences of racism in the game at SRTRC's fifteenth anniversary event at UNISON HQ on 3 August 2011. Curtis Fleming is also a patron of the charity Justice First and took part in a fundraising event at Goals Soccer Saturday with his team The Misfits losing 5–2 in the final to Hope athletic. Despite this Curtis graciously handed over the trophy to the winners.
Coaching career
Fleming later coached at youth level at Middlesbrough and joined Livingston in June 2007, as assistant manager to Mark Proctor. In July 2011, Fleming joined former club Crystal Palace, managed by former Eagles teammate Dougie Freedman, as Development Coach. In July 2012, Fleming was promoted to the role of first team coach at Crystal Palace, yet moved on four months later to join Freedman in a similar role at Bolton Wanderers. In February 2016, Fleming joined former Boro teammate Craig Hignett at Hartlepool United as Assistant Manager. After less than a year at Hartlepool he was headhunted by Ian Holloway in December 2016 and moved to Queens Park Rangers as Assistant Manager. He moved to Middlesbrough as First Team coach in 2018 and left the club after the departure of Tony Pulis in May 2019. In 2019 he appointed as the reserve team coach of indian club Punjab FC for 2019-2020 season. In 2020 June 15 he appointed the head coach of the main team.
