Born Charles Elphinstone on 18 June 1774, Fleming was the son of John Elphinstone, the 11th Lord Elphinstone. He assumed the name Fleming on the death of his grandmother, the only surviving child of John, 6th Earl of Wigtoun, and he succeeded to the family’s estates. Fleming entered the Navy and by the age of 20 had reached the rank of Commander. He subsequently entered politics, being elected a member of Parliament for the constituency of Stirlingshire on 13 January 1802.

With the outbreak of the Napoleonic Wars in 1803 Fleming returned to active service and commanded a number of ships including HMS Revenge, HMS Bulwark and HMS Standard. Fleming was appointed a Colonel of the Royal Marines on 12 August 1812 and reached flag rank with a promotion to rear-admiral on 4 December 1814. He was appointed commander-in-chief at Gibraltar in 1814 and became the first Master of the Royal Calpe Hunt. Fleming continued to rise through the ranks after the end of the wars with France. He was made a vice-admiral on 19 July 1821, was in command at the West Indies by 1828, and became an admiral in 1837. He returned to politics following his retirement from active service, regaining his Stirlingshire seat hi 1832 and holding it until 1835. Fleeming was Commander-in-Chief, West Indies from 1828 to 1829, Commander-in-Chief, The Nore from 1834 to 1837 and briefly Commander-in-Chief, Portsmouth from April to November 1839. He succeeded Sir Thomas Hardy as Governor of Greenwich Hospital in September 1839, a position he held for the remainder of his life.

Fleeing married Doña Cataline Paulina Alesandro de Jiminez in June 1816 in the Cathedral of Santa Cruz in Cadiz, Spain: she was 16, he was 42. Their marriage produced a son and four daughters. He died from influenza in Leamington Spa on 30 October 1840.