Отец — Конрад Фридрих Толь (1749—1821).
Службу начал в 1796 году. Воспитывался в сухопутном кадетском корпусе, откуда выпущен был в свиту Его Величества по квартирмейстерской части (генеральный штаб); боевое поприще начал в швейцарском походе Суворова; участвовал в войне 1805 года против французов и в турецких кампаниях 1806 и 1809 годов.
Принял участие в войнах с Францией. В 1812 году Толь был назначен генерал-квартирмейстером 1-й армии и оставался на этом месте до отступления русских из Москвы, а затем исправлял должность генерал-квартирмейстера главной армии, причем все события Отечественной войны, с 6 октября, совершались при непосредственном и весьма деятельном его участии. В декабре 1812 года Толь назначен был генерал-квартирмейстером главного штаба Его Величества; в 1814 году участвовал в сражениях под Бриенном, Фер-Шампенуазом и Парижем.
В турецкую кампанию 1829 года Толь состоял начальником штаба армии графа Дибича; его распоряжения немало способствовали успешному окончанию войны, которое доставило ему графское достоинство и орден Святого Георгия 2-й степени.
Был участником подавления восстания декабристов. В начале 1830 года назначен членом Государственного совета, а в конце того же года — начальником штаба армии, посланной для усмирения польского восстания. В сражении под Гроховым Толь много содействовал победе, но ему не удалось склонить Дибича к немедленному затем штурму Праги. По смерти И. И. Дибича Толь, до прибытия Паскевича, временно командовал армией. Во время штурма Варшавы, когда Паскевич был контужен, и командование армией опять перешло к Толю, он ввёл российские войска в столицу Польши.
С 1833 года Толь был главноуправляющим путями сообщений и публичными зданиями. Именно Толь принимал решение о выдаче разрешения на строительство Царскосельской железной дороги Ф. А. Герстнеру. Это решение базировалось на выводах комиссии во главе с М. М. Сперанским
К. Ф. Толь был корреспондентом Пушкина; в одном из своих последних писем (накануне дуэли с Дантесом) Пушкин благодарит Толя за доставленные им сведения о И. И. Михельсоне и приводит по поводу незаслуженно забытого военачальника библейскую цитату: «Истина сильнее царя».