In March 1847 he began working at the Western Bank of Scotland in Glasgow, leaving in 1852 to set up his own legal practice.
His investigation of financial irregularities at the bank led to it ceasing trading in November 1857 (a major scandal of the day).
During the next ten years Fleming made major improvements to the company, bringing it to the forefront of Scottish banking.
This included a critical move in 1873 to establish a base in London requiring a change in the original 1727 legal conditions upon the bank, limiting it to practice only in Scotland.
In 1875 Fleming's knowledge successfully fended off a challenge by the English banks, objecting to the Scottish invasion.