Родился 24 августа (5 сентября н.с.) в Петербурге в знатной дворянской семье. Родители разошлись сразу после рождения сына; он воспитывался матерью и ее братом — писателем А. Перовским (псевдоним А. Погорельский). Детские годы прошли в имениях матери, позже дяди на Северной Украине. Получил хорошее домашнее образование.
В 17 лет он был зачислен в Московский архив Министерства иностранных дел, затем был на дипломатической службе в Германии. В 1843 получил звание камер-юнкера.
Литературным творчеством Толстой занимался с раннего возраста, поощряемый своим дядей. Писал стихи, фантастические повести, и уже его первая опубликованная под псевдонимом "Краснорогский" в 1841 повесть "Упырь" была замечена Белинским.
В 1840-е годы он начал работать над историческим романом "Князь Серебряный", оконченным в 1861. В этот же период написал рад баллад и лирических стихотворений, получивших широкую известность и впоследствии положенных на музыку русскими композиторами ("Колокольчики мои", "Ты знаешь край, где все обильем дышит", "Курган", "Средь шумного бала..." и др.).
В 1854 вместе со своими двоюродными братьями Жемчужниковыми создал сатирическую литературную маску Козьмы Пруткова и сборник его сочинений, до сих пор популярный в России.