Lestocq was born on 16 August, 1738, in Celle, the son of a Prussian officer of Huguenot descent. In 1757 he joined the Berlin Gensd'armes regiment as a Fahnenjunker. During the Seven Years War he took part in the battles of Zorndorf, Kunersdorf and Torgau. After distinguishing himself at Langensalza he was awarded the Pour le mérite order in 1761. In 1768 he was promoted to Premierleutnant and moved to the Hans Joachim von Zieten's Husarengenerals regiment. He became Zieten's Adjutant, progressing through the ranks from Stabsrittmeister, Major, Oberstleutnant to Oberst. In 1792, king Friedrich Wilhelm II made him Batallionskommander of the von Eben regiment (Husarenregiment Nr. 2).
During the wars of the First Coalition against France he fought at Kaiserslautern, Morsbrunn and Trippstadt. In 1794 he became commander of the Husarenregiment Nr. 2. After the peace of Basle in 1795 his regiment was stationed as a security force on the franco-westphalian border. Lestocq then became Generalmajor and in 1803 stationed in New East Prussia. He took general command of Prussian troops in the region and also became commander of Husarenregiment Nr. 9. In 1805 he was promoted to Generalleutnant. In 1807 he was at Eylau with his chief of staff Gerhard von Scharnhorst and was as a result awarded the Order of the Black Eagle. Lestocq's relative success at Eylau was attributed to Scharnhorst's planning, and for which the latter was to be awarded the Pour le mérite order. After the defeat at Friedland Lestocq was appointed by the king to sit on the commission for Prussian unity. On 12 November 1808 he was appointed governor of the Berlin Residenz and in 1814 he became governor of Breslau.
He died in Berlin on 1 January 1818 and was buried seven days later in the cemetery of the Berlin Garnisonkirche.