Natzmer was born in Gutzmin, Further Pomerania, into a noble family of Kashubian descent dating to 1202. He was the son of Joachim Heinrich von Natzmer, the district president of Schlawe, and Barbara von Weyer. The Natzmers of Pomerania were commemorated with the villages of Natzmershagen and Natzmersdorf near Schlawe and Labes.
Natzmer was married twice, first to Sophie von Wreech and then to Charlotte Justine von Gersdorff. He had two sons from his second marriage, Carl Dubislav (died 1737) and Heinrich Ernst (died 1739). Because both sons died before their father, the Pomeranian branch of the Natzmer family ended after Dubislav Gneomar died in Berlin. Other branches of the family possessed estates throughout Brandenburg, Saxony, and Silesia; ten members of the Natzmer family served in the Fourth Coalition against Napoleon Bonaparte. One of Emperor William I's closest friends was Oldwig von Natzmer.
After entering Dutch service as a youth, Natzmer joined the army of Brandenburg-Prussia in 1677 as a lieutenant in Oberstleutnant Joachim Ernst von Grumbkow's Elite-Eskadron-Dragonern. Natzmer took part in the siege of Stettin and other battles against Sweden, at times as the adjutant of Georg von Derfflinger. Promoted to Stabshauptmann in 1680, he participated in the Great Turkish War in 1686, after which Elector Frederick William named him Generaladjutant.
Natzmer formed a new regiment of German nobles known initially as the Grands Mousquetaires and later as the Gensdarmes. As Oberstleutnant, he was the first commander of the regiment. They served Holland's House of Orange against King Louis XIV of France in the War of the Spanish Succession, campaigning in Brabant, Luxembourg, and Flanders. He was taken prisoner during the Battle of Höchstädt in 1703, but released shortly after.
Promoted to Generalmajor, Natzmer led the Prussian cavalry in the Battle of Blenheim, in which he was seriously wounded. Before this battle, he was consulted for his excellent knowledge of the battlefield, which was the same as in the Battle of Höchstädt.
He served with distinction as Generalleutnant in the battles of Malplaquet and Oudenaarde. Natzmer was awarded the Order of the Black Eagle in 1714 and promoted to General der Kavallerie after the capture of Stralsund. In 1728 he became a Prussian Generalfeldmarschall.
After Crown Prince Frederick's unsuccessful flight from his father, Natzmer was ordered to apprehend Frederick's friend and conspirator, Hans Hermann von Katte. Hesitant to stop the youth, he granted Katte three hours to burn any incriminating documents and escape. Frustrated by Katte's procrastination even with the extra window of time, Natzmer reluctantly arrested the accused, whom Frederick William II eventually sentenced to death. When the furious king considered executing Frederick, Natzmer was among his councillors who advised clemency.
While at Küstrin in 1731, Frederick wrote Natzmer a letter positing Prussian annexation of Polish Royal Prussia in order to connect East Prussia and Prussian Pomerania; "Frederick the Great" would create West Prussia from that territory after the 1772 First Partition of Poland.