В связи с окончанием «Введения» Карамзин писал М. Н. Муравьеву: «За приятнейшую должность поставляю себе давать вам отчет в моей работе. Я кончил теперь введение, которое состоит в ответе на вопросы: кто были древние обитатели в России? кто были наши предки славяне, варяги и варяги-Русь? то есть я дошел до времен Рюрика и могу сказать, что этот шаг был самый труднейший. Надлежало сообразить все написанное греками и римлянами о наших странах, от Геродота до Аммиана Марцеллина; все написанное византийскими историками о славянах и других народах, которых история имеет некоторое отношение к Российской. Нелегко было также сообразить все, предложить следствия кратко, просто и ясно; не сказать ничего лишнего, не пропустить ничего существенного; всякое слово основать на историческом свидетельстве и вероятность отличить от действительной истины. Описание физического и нравственного характера древних славян, их правления и веры составит второе отделение, которым уже занимаюсь, выбрав материалы из византийских летописцев и других, однако ж, достоверных авторов. Надеюсь, если буду жив и здоров, кончить эту статью нынешнею зимою; и тогда уже приступлю к действительной Российской Истории, к описанию правления князей варяжских в нашем отечестве. Одним словом, не только единственное мое дело, но и главное удовольствие есть теперь История. Думаю, что Бог поможет мне совершить начатое не к стыду века».
В ноябре 1805 года Карамзин завершил работу над вторым томом, охватывающим время от Рюрика до Владимира Святого и введения христианства (впоследствии оба этих первоначальных тома были объединены в один — первый).
Сообщая М. Н. Муравьеву в марте 1806 года об окончании первоначального второго тома, Карамзин рассказывает о планах будущей работы: «Я кончил второй том, поместив в нем историю времен язычества, от первых князей варяжских до смерти Владимира, и заключив его обозрением гражданского и нравственного состояния древней России. По сю пору все идет изрядно; увидим, что будет далее. Каждая эпоха имеет свои затруднения. Надеюсь в III томе дойти до Батыя, а в IV до первого Ивана Васильевича; там остается еще написать тома два до Романовых».
Весь 1806 год Карамзин писал третий том, 1807-й — четвертый. «Работа моя, — сообщает он брату осенью 1806 года, — подвигается вперед, хотя и медленно. Ежели буду жив и здоров с моим семейством, то надеюсь зимою дойти до татарского ига. Жаль, что я не моложе десятью годами! Едва ли Бог мне даст довершить мой труд: так много еще впереди».
Осенью 1807 года умер М. Н. Муравьев. Для Карамзина это была тяжелая потеря. В последнее десятилетие Муравьев был, пожалуй, одним из самых близких ему людей. Несколько лет спустя Карамзин подготовил и издал двухтомник его сочинений.
В мае 1808 года Карамзин пишет письмо H. Н. Новосильцеву — президенту Академии наук, попечителю Санкт-Петербургского учебного округа, в то время занявшему должность статс-секретаря императора, руководившему его личной канцелярией и делами, подведомственными «непосредственному самого государя усмотрению и разрешению». Фактически это письмо было отчетом Александру.