Сын бранденбургского тайного советника. Окончил академический курс наук и в 1688 году путешествовал в Англию. После чего поступил на военную службу. Боевое поприще начал в войнах против Людовика XIV. В 1689 и 1690 годах находился при осаде Кейзерсверта и Бонна, в 1691 году в сражениях при Флёрусе и Лёзе, в 1693 году в деле при Гейльброне, а потом сражался под начальством маршала Шомберга в сражениях при Марсели и в Пьемонте.
Саксонский курфюрст Иоганн-Георг IV пожаловал его своим генерал-адъютантом и полковником. Эту должность Флеминг сохранил и при курфюрсте Августа, оказав ему важные услуги как в некоторых поручениях в Венгрии и Вене, так и на польском сейме 1697 года, на котором Август был избран в короли Польши, за что произведен в генерал-майоры, тайные военные советники и генерал-почтмейстеры Саксонии, и обер-шталмейстером Литовским.
За храбрость в 1702 году при Мариенбурге и Динабурге и в 1705 году при Клисове пожалован в генерал-от-кавалерии.
В 1707 году назначен губернатором Дрездена, Кёнигштейна, Зоненштейна и главным командиром королевской гвардии.
За отличия Флемминга во время Северной войны, он в 1710 году стал генерал-фельдцейхмейстером Польши, президентом тайного и военного советов, а в 1712 году генерал-фельдмаршалом Польши и звание кабинет-министра. Он был награжден датским орденом Слона, русским орденом Святого Андрея, Мальтийским крестом и Орденом Белого Орла.
В 1712 году командовал при Гадебуше, был при взятии Тенингена, завоевал Замостье и разбил польских мятежников при Сандомире.
Он присутствовал при свидании польского короля с Петром I в Данциге, а также на конгрессах в Люблине и Варшаве, после чего назначен был главным губернатором всех польских областей и шефом гвардии и драгунского полка.
Позже Флемминг выказал себя искусным дипломатом, устроив в Вене бракосочетание курпринца Фридриха Августа с эрцгерцогиней Марией Жозефиной, а также участвовал при заключении союзного договора между его государем, императором Карлом VI и английским королем Георгом I.