Totleben was born in Tottleben, Thuringia, and served at the court of Augustus III, King of Poland and Elector of Saxony. He fled Saxony after being accused of corruption. He then served for various periods at the courts of Saxe-Weissenfels, Bavaria, the Dutch Republic during the War of the Austrian Succession, and the Kingdom of Prussia. In 1747 he is mentioned as commander of a regiment of infantry of the Dutch Republic, but the regiment existed only on paper and was never realized. By then he already had a reputation as a scoundrel.
Count Totleben entered the Russian service during the Seven Years’ War (1757-1763). He distinguished himself at the Battle of Kunersdorf (1759) and was promoted to General. Totleben gained particular fame for his brief occupation of the Prussian capital Berlin in 1760. Shortly, the advance of Frederick the Great’s Prussian army forced him to retreat, however. In June 1761, he was accused of treachery and arrested in Pomerania. Sent in chains to St. Petersburg, he was sentenced to death via quartering, but Empress Catherine the Great pardoned him in 1763. Nevertheless, Totleben was deprived of all his titles and awards and sent into exile abroad (or to Siberia, according to one account).