В то же время анекдотический случай, положенный в основу произведения, носил жизненный характер. Факты скупки «мертвых душ» были достаточно распространены в тогдашней России и могли быть известны Гоголю и ранее. Об одном из них рассказывает, например, дальняя родственница писателя Мария Григорьевна Анисимо-Яновская. Но как бы там ни было, Гоголь принялся за большое сочинение по совету Пушкина. Знаменательна и ссылка последнего на Сервантеса, приобретшего мировую известность после написания «Дон Кихота». Отныне судьба и слава Гоголя будут неразрывно связаны с «Мертвыми душами».
Переписка Гоголя, его автобиографические заметки и свидетельства современников дают возможность восстановить ход работы над поэмой с достаточной полнотой. По словам Гоголя, он принялся за нее, не имея поначалу определенного плана, не давши себе отчета, что такое должен быть сам герой. «Я думал просто, что смешной проект, исполнением которого занят Чичиков, наведет меня сам на разнообразные лица и характеры; что родившаяся во мне самом охота смеяться создаст сама собою множество смешных явлений, которые я намерен был перемешать с трогательными».
Набросав первые главы, Гоголь прочел их Пушкину, и поэт, который всегда смеялся при его чтении, становился все сумрачнее и сумрачнее и наконец сделался мрачен. По окончании чтения он произнес с тоской: «Боже, как грустна наша Россия!» В этой связи Гоголь заметил для себя: «Меня это изумило. Пушкин, который так знал Россию, не заметил, что все это карикатура и моя собственная выдумка! Тут-то я увидел, что значит дело, взятое из души, и вообще душевная правда…»
Озадаченный тягостным впечатлением, которое произвело начало поэмы на Пушкина, Гоголь принялся за его переработку. 12 ноября (н. ст.) 1836 года он писал Василию Андреевичу Жуковскому из Парижа: «Все начатое переделал я вновь, обдумал более весь план и теперь веду его спокойно, как летопись. <…> Если совершу это творение так, как нужно его совершить, то… какой огромный, какой оригинальный сюжет! Какая разнообразная куча! Вся Русь явится в нем! Это будет первая моя порядочная вещь, которая вынесет мое имя». Из письма видно, как по мере обдумывания плана разрастается замысел, Гоголь проникается ощущением значительности своего сочинения: «Огромно велико мое творение, и не скоро конец его».