Родился в дворянской прусской семье офицера. Получил образование дома, затем в реальной гимназии при интернате монастыря Локкум. Во время Первой мировой войны 1917 в возрасте 16 лет добровольно поступил в армию. В составе 1-го гвардейского пехотного полка участвовал в боях на Западном фронте, в июне 1918 был произведён в лейтенанты, в июле награждён Железным крестом. В 1919 служил во фрайкоре (Добровольческом корпусе) — военизированном формировании, боровшемся против леворадикальных сил, был участником подавления революционного движения в Берлине. В 1920 был демобилизован, изучал банковское дело, затем учился на юридическом факультете Берлинского университета и одновременно успешно работал биржевым маклером. Совершил годичную зарубежную поездку.
В 1924 поступил на службу в рейхсвер, был зачислен лейтенантом в 9-й пехотный полк (Потсдам). Первоначально молодой офицер, как и многие его сверстники, испытывал симпатии к национал-социализму, но после «Ночи длинных ножей» 1934 он дистанцировался от нацистов. В 1936 окончил (первым в выпуске) военную академию и был направлен в Оперативное управление Генерального штаба. Там пришёл к выводу об опасности, к которой могла привести для Германии перспектива войны на два фронта, и стал противником агрессивной внешней политики нацистов. После кризиса начала 1938 (когда в отставку были отправлены противники агрессии) установил контакты с тайными оппозиционными группами, намеревавшимися отстранить Гитлера от власти.
Будучи кадровым прусским офицером, являлся противником милитаризма, при возможности предпочитал ходить в штатской одежде. В 1943 говорил своим двум сыновьям во время их конфирмации в Потсдамской гарнизонной кирхе:
Во время польской кампании 1939 был 1-м офицером Генерального штаба (начальником оперативного отдела) в штабе 118-й пехотной дивизии, награждён за боевые отличия Железным крестом 1-го класса. В середине октября 1939 получил назначение в штаб группы армий «А» (командующий — Герд фон Рундштедт), занимавшийся разработкой операций во Франции. С 1941 служил 1-м офицером Генерального штаба в штабе группы армий «Центр» (командующий — Фёдор фон Бок, затем Ханс Гюнтер фон Клюге) на Восточном фронте. Резко негативно относился к репрессиям в отношении евреев и политработников Красной армии, пытался опротестовать эти приказы. Говорил своему сослуживцу полковнику барону Рудольфу фон Герсдорфу, что если приказы о расстрелах комиссаров и «подозрительных» гражданских лиц не будут отменены, то
В октябре 1943 стал командиром полка, но уже в следующем месяце был назначен начальником штаба 2-й армии. Был награждён Немецким крестом.
Начиная с 1942 готовил убийство Гитлера, в феврале того же года установил контакт с участниками заговора в Берлине. Был одним из главных организаторов попытки покушения на Гитлера в Смоленске 13 марта 1943, когда в самолёт фюрера была заложена замаскированная под посылку бомба, которая, однако, не взорвалась (считается, что взрыватель не сработал из-за слишком низкой температуры в багажном отделении).
Неудачно пытался организовать свой перевод в Ставку Гитлера, надеясь там организовать на него покушение. В конце 1943 фон Тресков попросил фельдмаршала Эриха фон Манштейна, который высоко ценил его способного штабного работника, перевести его в штаб группы армий «Юг», рассчитывая на то, что это также поможет ему в организации покушения. Однако Манштейн, зная о ярко выраженных антинацистских взглядах фон Трескова, отказался удовлетворить его просьбу.
Система связей фон Трескова в рамках заговора была весьма обширной — он общался как с Карлом Фридрихом Гёрделером, так и с графом Клаусом Шенком фон Штауффенбергом, с которым встречался во время службы на Восточном фронте.
Узнав о неудаче антинацистского выступления военных 20 июля 1944 и понимая неизбежность ареста, фон Тресков сказал своему адъютанту Фабиану фон Шлабрендорфу, также участвовавшему в заговоре: «Они скоро узнают про меня и постараются вырвать из меня имена наших товарищей. Чтобы предупредить их, я должен пожертвовать жизнью». Шлабрендорф не смог убедить его отказаться от самоубийства, которое генерал пытался замаскировать, имитируя гибель в бою, чтобы спасти от преследований членов своей семьи. Шлабрендорф позднее передал слова фон Трескова, сказанные им незадолго до смерти:
21 июля 1944 фон Тресков отправился к линии фронта, вышел на нейтральную полосу, выстрелами из пистолета имитировал бой, а затем взорвал себя ручной гранатой.
Останки фон Трескова были первоначально похоронены на родине, но когда его роль в заговоре выяснилась, эксгумированы и сожжены в крематории концлагеря Заксенхаузен. Родственники генерала подверглись репрессиям.
В современной Германии фон Тресков считается героем антинацистского сопротивления, в его честь названа казарма бундесвера.
В фильме операция «Валькирия» роль фон Трескова сыграл актер Кеннет Брана.