Сюжет «Мертвых душ», как и сюжет «Ревизора», был подсказан Гоголю А. С. Пушкиным. Этот сюжет, по всей вероятности, вырос из пушкинского письма от 16 февраля 1831 года П. А. Плетневу: «Через несколько дней я женюсь: и представляю тебе хозяйственный отчет: заложил я моих 200 душ, взял 38 000 рублей – и вот им распределение: 11 000 теще, которая непременно хотела, чтоб дочь ее была с приданым – пиши пропало. 10 000 Нащокину, для выручки его из плохих обстоятельств: деньги верные. Остается 17 000 на обзаведение и житие годичное. В июне буду у вас и начну жить en bourgeois, а здесь с тетками справиться невозможно – требования глупые и смешные – а делать нечего. Теперь понимаешь ли, что значит приданое и отчего я сердился? Взять жену без состояния – я в состоянии, но входить в долги для ее тряпок – я не в состоянии». В «Мертвых душах» Чичиков мечтает заложить скупленные у помещиков мертвые души в Опекунский совет, чтобы зажить вполне буржуазной жизнью и иметь за собой «приданое», чтобы жениться на губернаторской дочке.
Именно Чичиков – не только главный герой, но и тот стержень, на котором держится сюжет и действие «Мертвых душ». Как иронически подчеркивает Гоголь, «не приди в голову Чичикова эта мысль (накупить «всех этих, которые вымерли», и заложить их в Опекунский совет. –
По утверждению дальней родственницы Гоголя Марьи Григорьевны Анисимо-Яновской, сюжет поэмы также имел свои корни в родной для писателя Миргородчине: «Мысль написать «Мертвые души» взята Гоголем с моего дяди Пивинского. У Пивинского было 200 десятин земли и душ 30 крестьян и детей пятеро. Богато жить нельзя, и существовали Пивинские винокурней. Тогда у многих помещиков были свои винокурни, акцизов никаких не было. Вдруг начали разъезжать чиновники и собирать сведения о всех, у кого есть винокурни. Пошел разговор о том, что у кого нет пятидесяти душ крестьян, тот не имеет права курить вино. Задумались тогда мелкопоместные: хоть погибай без винокурни. А Харлампий Петрович Пивинский хлопнул себя по лбу да сказал: «Эге! не додумались!» И поехал в Полтаву да и внес за своих умерших крестьян оброк, будто за живых. А так как своих, да и с мертвыми, далеко до пятидесяти не хватало, то набрал он в бричку горилки, да и поехал по соседям и накупил у них за эту горилку мертвых душ, записал их себе и, сделавшись по бумагам владельцем пятидесяти душ, до самой смерти курил вино и дал этим тему Гоголю, который бывал в Федунках, имении Пивинского, в 17 верстах от Яновщины; кроме того, и вся Миргородчина знала про мертвые души Пивинского».
7 октября 1835 года Гоголь писал из Петербурга А. С. Пушкину, подсказавшему ему сюжет поэмы: «Начал писать «Мертвых душ». Сюжет растянулся на предлинный роман и, кажется, будет сильно смешон. Но теперь остановил его на третьей главе. Ищу хорошего ябедника, с которым бы можно коротко сойтиться. Мне хочется в этом романе показать хотя с одного боку всю Русь».
О продолжении работы над «Мертвыми душами» Гоголь писал из Парижа В. А. Жуковскому 31 октября (12 ноября) 1836 года: «Осень в Веве наконец настала прекрасная, почти лето. У меня в комнате сделалось тепло, и я принялся за «Мертвых душ», которых было начал в Петербурге. Все начатое переделал я вновь, обдумал более весь план и теперь веду его спокойно, как летопись… Если совершу это творение так, как нужно его совершить, то… какой огромный, какой оригинальный сюжет! Какая разнообразная куча! Вся Русь явится в нем! Это будет первая моя порядочная вещь, вещь, которая вынесет мое имя. Каждое утро, в прибавление к завтраку, вписывал я по три страницы в мою поэму, и смеху от этих страниц было для меня достаточно, чтобы усладить мой одинокий день. Но наконец и в Веве сделалось холодно. Комната моя была нимало ни тепла; лучшей я не мог найти. Мне тогда представился Петербург, наши теплые домы, мне живее тогда представились вы, вы в том самом виде, в каком встречали меня, приходившего к вам, и брали меня за руку, и были рады моему приходу… и мне сделалось страшно скучно, меня не веселили мои «Мертвые души», я даже не имел в запасе столько веселости, чтобы продолжить их. Доктор мой отыскал во мне признаки ипохондрии, происходившей от гемороид, и советовал мне развлекать себя, увидевши же, что я не в состоянии был этого сделать, советовал переменить место…