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."