Signed from Oldham Athletic in June 1997 for £600,000, Craig can play as centre-back or as right-back. He began his career with hometown team Halifax where he made 57 league appearances before joining Oldham in August 1991. He made 164 league appearances for Oldham before joining the Canaries. Currently contracted until June 2003, Craig had made 208 appearances for Norwich as of the end of the 2001/02 season where he had been ever present

Craig signed a new two year contract in January 2003 which was a relief to Norwich fans as his contract was due to expire at the end of the season. He made his 500th professional appearance when he played in the 3-0 defeat to Wolves on 21st April 2003.

Although the headlines in Norwich's 2003/4 promotion season went to Darren Huckerby, England new boy Robert Green and new Scottish international Malky Mackay, the Carrow Road faithful recongised Fleming's contribution to a successful season and named him their Player of the Year for 2003/4

2005/6 is Craig's testimonial season and his chosen charity is The Matthew Project, a Christian charity aimed at drug outreach.

Having lost his first-place under Peter Grant during the 2006/7 season, it was reported that Bournemouth management team Kevin Bond and Rob Newman had been scouting his performances for the reserves to view whether to sign him for the South Coast club.

In January 2007, he joined Wolves on loan as emergency cover for their defence and made one appearance for them. He was recalled at the end of the month to sign for Rotherham on an 18month contract. Despite City's frailities in central defence, Grant said that Fleming could go if he had the offer of another professonal contract as his contract with City was due to expire at the end of the 2006/7 season. Fleming teams up with Alan Knill, a former colleague from Halifax who is now managing the Millers.

Fleming said “I would like first of all to give my heartfelt thanks to the Norwich fans for all their support during my ten seasons at Carrow Road and of course during my testimonial year. I really and sincerely hope they get the good times and the success they fully deserve in the years ahead. There have been some highs and lows during my time here but I've got some fantastic memories and I guess winning promotion in 2004 has to be the highlight. Norwich City has been a massive part of my life and it always will be. I'm just very grateful to the supporters and everyone who I've worked with at the club since I joined. I was always proud to pull on the green and yellow jersey.”

Fleming could not help Rotherham avoid relegation from League One, but instead of moping about it, he spent May 2007 on a 230mile charity Hike and Bike to raise £20,000 for two local charities - RadioBroadlandKids and the Matthew Project. The week-long marathon of cycling and walking will see him finish at Norwich's Chapelfield Plain on Sunday 20th May, after dropping into a series of supporting schools along the way. Former Canaries Jeremy Goss and Bryan Gunn will be joining Fleming on some days.

Although a first team regular during the five months after his signing for the Millers, he was informed by new Rotherham manager Mark Robins that he was not in his first team plans for the 2007/8 campaign and so by mutual accord, Craig left Rotherham on 30th August 2007. He was quickly linked with a move to Keith Webb's King's Lynn and indeed trained with them and had discussions with them about his joining the club. He signed for Lynn on 19th September 2007 and made his debut against Gloucester City on 22nd September 2007 scoring the first goal in a 2-1 win.

In March 2008, Fleming was forced to retire following continued ankle problems. A club statement said: "Lynn FC have confirmed that Craig Fleming has been forced to retire from football due to injury. Craig has been advised by his surgeon that if he were to play again he would risk further damage to his already injured ankle."

In August 2008, Craig joined Ridgeons League side Lowestoft as first team coach and said "“I don't see much difference in the standards here and that of King's Lynn - despite there being three leagues between them there is very little difference at all.” In his first season with Lowestoft, they won the Ridgeons League and the Suffolk Senior Cup and reached the semi-final of the FA Vase before losing to Whitley Bay 3-2 on aggregate. The following year, Lowestoft won the Ryman Division One (North) title. Town finished the campaign with more than 100 points and 100 goals to their name. Fleming was then linked in May 2010 to the vacant manager's position at Histon

On 10th February 2011, Fleming was linked to the managerial vacancy at Camrbidge United. He stayed at Lowestoft and took them to the Ryman League play-offs. He was promoted to the position of Director of Football at the end of May 2011

In May 2014, Fleming was part of the Lowestoft management team that won promotion to the Conference South.

In October 2014, Fleming had been approached to become part of the first team coaching set-up at Blackpool but the Lancashire side then sacked manager jose Riga and Fleming's prospects of a one year rolling contract were dashed.

At the end of February 2015, it was announced that Fleming would leave Lowestoft Town to become an academy coach at Southampton working with their under-18s. Since Fleming’s arrival, six Under-18 player have gone on to play for the Saints’ first team. Fleming’s success saw him promoted in July 2018 to become Assistant Under-23 Coach. Fleming said: “I’m definitely excited by the change. It’ll be working with players that I’ve worked with for the past two or three years, so there’s familiarity there.” On December 23rd 2019 he was promoted to First Team Coach ro support new Saints boss Ralph Hasenhüttl. This was made permanent at the end of June 2019.

He, along with Kelvin Davis and Dave Watson, were dismissed from their roles on 26th May 2022 as Southampton embarked on a shake up of their coaching team after winning just one of their last 12 games in the 2021/22 Premier League season. They have though kept with manager Ralph Hasenhuttl.

In August 2023 Fleming joined Derby's academy as Head of Academy Technical Development.

On 20th March 2024, Fleming left his role at Derby, taking up a new role as Ralph Hasenhüttl’s assistant coach at German top flight side  VfL Wolfsburg