Fleming made his debut for Wrexham as a substitute for Steve Evans on 21 January 2007 during a 1–1 draw with Darlington in League Two and made his first start on 18 February in a 0–0 draw with Chester City. During the 2008–09 season, under new manager Dean Saunders Fleming managed to claim a regular place in the first team and was rewarded with a contract extension.
Out of contract at the end of the 2009–10 season, Fleming left Wrexham to sign for Morecambe on 27 July 2010. He made his debut for the club in a 2–0 win over Coventry City in the Football League Cup, scoring both goals, becoming the first player to score at Morecambe's new stadium the Globe Arena. However, Wrexham felt they deserved compensation as they had also offered Fleming a contract. The matter was referred to a tribunal, however they ruled no compensation was required as Wrexham failed to offer a contract that was equal to the terms of the deal Fleming was on previously.