Старший сын барона Карла Адольфа и баронессы Эльзы Софии фон Тотлебен (старый тюрингский род, влиятельный уже с XVI века, фамилия Тотлебен происходит от девиза «Treu auf Tod und Leben» (приблизительный перевод: верен не на жизнь, а насмерть), которому граф Тотлебен, похоже, по жизни не слишком следовал), в отрочестве был пажом при дворе саксонского курфюрста и польского короля, вскоре стал камерюнкером, с 1742 года — советником юстиции при саксонском правительстве.
14 сентября 1745 года польским королем и саксонским курфюрстом Фридрихом Августом II он был возведён в графское достоинство.
После смерти первой жены, Иоганетты Софии фон Кропфф в 1743 году (от этого брака у Тотлебена трое детей, из которых выжила лишь старшая дочь, Шарлотта Вильгельмина Иоганна, в замужестве баронесса фон Мирбах в Курляндии) женился на вдове графа Брониковского, владелице крупного поместья Вайстроп под Дрезденом, графине Элизабет Кристиане фон Зайфертиц. У них родился сын, граф Карл Адольф Готфрид фон Тотлебен, владетельный князь Вайстропа, впоследствии подполковник на прусской службе.
Готтлоб Курт Генрих был обвинён в коррупции и бежал, не дожидаясь результатов расследования, из Саксонии, после чего был заочно приговорён к пожизненному изгнанию.
После неудачной попытки поступить на баварскую службу Тотлебен уехал в Голландию, где в 1747 году ему удаётся получить патент полковника.
Во время войны за австрийское наследство (1740—1748) в Нидерландах с французами, в 1747 году вторгнувшимися в страну, пехотный полк Тотлебена в боевых действиях участия не принимал, находясь в тылу, в окрестностях Бреды. После войны полк переводится на гарнизонную службу в Штеенбергене, вскоре затем расформировывается. За Тотлебеном сохраняется полковничья пенсия.
Отсутствие военных успехов Тотлебен возмещал победами на амурном фронте, развлекающими европейских читателей ещё спустя полстолетия. Он соблазнил и похитил пятнадцатилетнюю единственную наследницу миллионного состояния Марию Петронеллу Гратьенн Виктор. Бегство из Голландии, где Тотлебен объявлен был в розыск, было осуществлено в лучших традициях приключенческого жанра: любовники четырежды переправлялись с одного берега Рейна на другой, чтобы сбить погоню со следа.
1 мая 1751 года Тотлебен подал прошение о разрешении проживания в Пруссии. После смерти второй жены он женился на Марии Виктор и переселился в Берлин, где, благодаря вновь приобретённому богатству и графскому титулу, он был хорошо принят при прусском дворе. Он планировал перейти на прусскую службу.
Однако, устав от неверности и мотовства мужа, Мария Виктор подала в 1755 году на развод. Развод был скандальным, сам Фридрих II был вынужден вмешаться в выяснение отношений между супругами. За возмутительные речи против двора, принявшего сторону жены, Тотлебен получил предписание покинуть Берлин.
Изгнанный из Пруссии, Тотлебен безуспешно пытался сформировать пехотный полк для австрийцев. Затем он вернулся в Голландию, где установил контакт с русским посланником и получил предложение сформировать добровольческий корпус для России. Он оставил голландскую службу и переехал в Санкт-Петербург.
По сведениям немецкого биографа, по указу от 1 (12) марта 1757 года Тотлебен получил право на формирование двенадцатитысячного корпуса и чин генерал-майора. По другим, более надёжным сведениям, он первоначально был волонтёром и лишь в 1759 году, в знак признания проявленной доблести, был принят в российскую армию сразу генерал-майором (что достаточно необычно, так как Тотлебен перескочил тем самым, по крайней мере, через одно воинское звание, а именно, бригадира).
В сражениях Семилетней войны (1756—1763) Тотлебен, не имевший до того времени боевого опыта (в написанном собственноручно послужном списке, сообщает о своём участии в чине капитана кавалерии в боевых действиях начального этапа Войны за австрийское наследство, эти данные, однако, по всей вероятности, присочинены им для придания послужному списку большей солидности) приобрёл репутацию храброго и способного командира летучих кавалерийских отрядов, «лихого саксонца на русской службе». Дважды он был ранен, в том числе сабельным ударом по голове, контужен «бомбою в том же месте головы», награждён орденом Св. Анны первого класса за Кунерсдорф (на своем портрете граф изображен с нагрудным знаком ордена Св. Анны) и ? 7 сентября (27 августа) 1760 года — орденом Александра Невского за успешный бой с арьергардом прусского принца Генриха. Командуя казаками, неоднократно отличился в стычках (в тогдашней терминологии «шармицелях») и набегах т. н. «малой войны». После одной из таких стычек, где Тотлебен чуть не утонул при переправе, получает предупреждение командующего фельдмаршала Бутурлина «впредь в подобныя отваги не вдаваться, но паче оных остерегаться».
В сентябре 1760 года корпусу Тотлебена была поручена экспедиция против Берлина. 3 октября (ныне в этот день отмечается национальный праздник Воссоединения Германии) (22 сентября) казаки Тотлебена появились под стенами прусской столицы. В ответ на отказ от предложенной капитуляции, Тотлебен без особого успеха бомбардировал город, затем, тремя колоннами, две из которых так и не вступают в бой, а третья, под началом будущего фельдмаршала князя Прозоровского, с большими потерями отбита, пытался взять его штурмом.
Расстреляв все боеприпасы, он был вынужден отступить к местечку Кёпеник (ныне район Берлина), где дожидался подхода определенных в поддержку корпусов генерал-поручика графа Захара Чернышёва и австрийского корпуса графа Ласси. На седьмой день осады защитники Берлина предложили капитуляцию Тотлебену, формально, как генералу, первым осадившему город, в действительности же рассчитывая на большее снисхождение от бывшего берлинца. Даже не известив старшего по званию Чернышёва, Тотлебен подписал капитуляцию от своего имени, и, назначив берлинским комендантом подчинённого ему бригадира Бахмана, занял город солдатами своего корпуса, чем навлекает гнев поставленных перед свершившимся фактом Чернышёва и Ласси, также претендующих на славу покорителей прусской столицы, и подозрения (безосновательные) в сговоре с врагом. Взяв с города контрибуцию, пленных, разорив военные предприятия, союзники покинули Берлин при известии о приближении Фридриха II с основными силами пруссаков.
За берлинскую экспедицию представляется к ордену Александра Невского и званию генерал-поручика, однако, по неясным причинам, не получает ни того, ни другого, а лишь грамоту с благодарностью за исполненный долг (генералы Чернышёв и Панин были за ту же операцию награждены орденами и повышены в чинах). Без ведома командования российской армии Тотлебен опубликовал в Варшаве сочинённую им «Реляцию» о взятии Берлина, где, наряду с преувеличением собственных заслуг, нелестно отзывается о своих конкурентах Чернышёве и Ласси. Бутурлину он заявил, что скорей умрёт, чем откажется от своей «Реляции», так как «там всё правда». В ответ на требование из Санкт-Петербурга извиниться перед Чернышёвым он подал в отставку, однако отставка заслуженного генерала не была принята и Тотлебен был назначен командующим всеми российскими лёгкими войсками.
С берлинской экспедицией связана легенда, упоминаемая А. С. Пушкиным в «Истории пугачевского бунта», о том, что Тотлебен, будто бы заметив сходство Пугачёва, участвовавшего в экспедиции в качестве простого казака, с наследником российского престола, будущим императором Петром III, подал Пугачёву тем самым мысль стать самозванцем.
В феврале 1761 года, пользуясь предоставленными командованием полномочиями на ведение переговоров с противником, Тотлебен установил переписку с принцем Генрихом Прусским и самим Фридрихом II. В результате задержания курьера с шифрованным посланием к Фридриху, Тотлебен был арестован 30 июня (19 июня) 1761 года в городе Бернштайн и обвинён в измене.
На допросах в тайном повытье он показал, что намеревался, завоевав доверие Фридриха, заманить прусского короля в ловушку и захватить его. Учитывая авантюризм и неумеренное честолюбие Тотлебена, можно признать такое объяснение, которому следствие не поверило, правдоподобным, тем более, что сохранившиеся в прусских архивах письма Тотлебена к Фридриху подтверждают его показания на допросах: сведения, сообщаемые пруссакам, являлись неполными, неверными или устаревшими к моменту отправки. Единственным результатом информации, полученной от Тотлебена, явилась неудачная экспедиция корпуса фон Цитена в Польшу в июле 1761 года (Цитен не нашёл в Польше разрозненных российских отрядов, о которых сообщалось Тотлебеном, и вынужден повернуть назад, так ничего и не совершив).
Распространенная легенда, упоминаемая в «Истории» С. М. Соловьева, гласит, что через Тотлебена передавались письма Фридриху от наследника российского престола, будущего Петра III. Своим возникновением она обязана не заслуживающим никакого доверия рассказам самого Петра. Всё время его короткого правления Тотлебен провёл в заключении. В переписке Тотлебена с Фридрихом имя наследника ни разу не упоминается.
В 1763 году Тотлебен был осуждён военным судом на смертную казнь, но был помилован Екатериной II. Согласно Указу, опубликованному в Москве 22 апреля (11 апреля) 1763 года, он был приговорён за «вредные намерения» против Российского государства к лишению всех чинов и наград и пожизненному изгнанию из пределов России. В чём состоят «вредные намерения» в Указе не разъясняется. Большинство современников связывало опалу популярного генерала с происками завистников, не простивших ему славы покорителя Берлина, и, в первую очередь, с именем графа Захара Чернышёва.
Указом Екатерины был снят секвестр с недвижимого имущества Тотлебена и его денежных вкладов в Гданьске и Гамбурге (формулировка Указа: «якоже мы в оном имении никакого участия желать не имеем»), Тотлебену было выплачено полное генеральское жалование за месяц-два перед арестом и, с вычетами, за всё время пребывания в заключении. В сопровождении премьер-майора Мезенцева и знающего немецкий язык прапорщика Реэра, а, также 6 рядовых, занятых перевозкой личных вещей генерала, изъятых при задержании и теперь возвращённых ему, Тотлебен был доставлен к российской границе, где и был оставлен 24 мая (13 мая) 1763 года «без абшида» в местечке Шульценкруг.
Какое-то время Тотлебен провёл в своих имениях, тяготясь однообразной жизнью сельского помещика. По другим сведениям, он скитался по всей Европе, скрываясь от кредиторов.
Затем Тотлебен, к изумлению современников, вернулся в Россию, где лишь недавно счастливо избежал казни. В России первоначально ему было разрешено проживание в городе Порхове, где на его содержание выдавалось из казны по рублю в день (фунт мяса стоил тогда в столице 5 копеек).
Тотлебен получил прощение, согласно некоторым сведениям, прослужив год рядовым на Кубани, где отличился храбростью при отражении набегов горцев. Необычайная по меркам того времени мягкость наказания, а также быстрое прощение и восстановление в прежних чинах, а затем и повышение в чине военного, чья измена была официально доказана и подтверждена опубликованным Высочайшим указом, представляют доныне загадку. Ряд авторов (Александр Горбовский, Юлиан Семёнов) полагают, что «предательство» Тотлебена являлось в действительности получившей нежелательную огласку тайной операцией, задуманной в Санкт-Петербурге. От Тотлебена пришлось временно избавиться, но заслуги его не были забыты теми высокими лицами, которые за ним стояли. Это предположение не подтверждается, но и не опровергается известными фактами. Интересно, что, разоблачивший измену Тотлебена подполковник Фёдор Аш закончил свои дни в заключении: он был арестован, будучи к тому времени отставным бригадиром, в 1777 году, просидел 19 лет в крепости Динамюнде и в 1797 году был помещён пожизненно в Спасо-Ефимьевский монастырь, где содержались душевнобольные государственные преступники.
В 1769 году во время русско-турецкой войны генерал-майор Тотлебен был направлен во главе отдельного отряда для ведения боевых действий против турок в Грузии.
В 1768 году в разгаре войны с Османской Империей Тотлебен был назначен в Закавказье, где Екатерина впервые создавала почву диверсий у турецких границ. Тотлебен был назначен главой первой организованной военной силы России которая прошла Дарьяльское ущелье. Ему было приказано воссоединиться с царем Грузии (Картли-Кахетии) Ираклием вторым. Последний надеялся с помощью России вернуть оккупированные Османами грузинские земли к югу от Куры. Но Тотлебен вскоре поссорился с грузинским царём и его генералами, которых он презирал из-за их восточного склада и просил отстранить всех грузинских офицеров из общей армии. Несколько русских офицеров сговорились против Тотлебена, который в свою очередь обвинял грузин в затее интриг. Отношения между Тотлебеном и Ираклием II-м ухудшились в апреле 1770 года, когда русско-грузинская армия шла против Ахалцихе, сильнейшей крепости Османов в Грузии. Тотлебен неожиданно отказался участвовать в бою и отозвав всех русских солдат и артиллерию оставил Ираклия одного на поле боя. В то время когда шел бой между грузинами и турками, Тотлебен, уверенный в явную гибель царя, пошел на Тбилиси объединившись в заговоре против престола Грузии с оппозиционными местными князьями. Несмотря на предательство, Ираклий II и его грузины наголову разбили армию турков в битве у Аспиндзы и планы Тотлебена не реализовались.
Тотлебен затем успешно воевал в Имеретии, взял ряд турецких крепостей, занял столицу княжества г. Кутаиси. Разбив 12-тысячный турецкий корпус, осадил город и крепость Поти.
Однако, невзирая на достигнутые военные успехи, отмеченные орденом Александра Невского (возложен самой императрицей в день Св. Александра Невского 10 сентября (30 августа) 1771 года, на обеде во дворце по этому случаю присутствует и генерал-аншеф З. Г. Чернышёв) с долгожданным званием генерал-поручика, Тотлебен был отозван Екатериной из-за распрей с союзниками — грузинскими князьями, наносящих, по мнению императрицы, вред влиянию России в регионе, в первую очередь, из-за вражды с царем Картли Ираклием II.
Затем Тотлебен командовал российскими нерегулярными войсками, казаками и башкирами, в Литве. В 1772 году генерал-поручик граф Тотлебен был направлен в Польшу, где принимает участие в войне с конфедератами, к которым одно время, после изгнания из России, он намеревался примкнуть.
Тотлебен умер от горячки в Варшаве. Он был похоронен со всеми воинскими почестями и к неудовольствию соотечественников-немцев по православному обряду и в православной часовне, несмотря на своё лютеранское вероисповедание.