Роман написан в 1950—1951 годах в лагере, на строительстве восточного крыла железной дороги Салехард — Игарка. Штильмарк начал писать его по просьбе лагерного старшего нарядчика Василия Павловича Василевского в обмен на освобождение от общих работ. Василевский надеялся послать роман Сталину и получить за это амнистию. Штильмарк зашифровал в тексте романа фразу «лжеписатель, вор, плагиатор», имея в виду Василевского. Её можно найти, если читать первые буквы каждого второго слова во фрагменте из двадцать третьей главы:
Листья быстро желтели. Лес, еще недавно полный жизни и летней свежести, теперь алел багряными тонами осени. Едва приметные льняные кудельки вянущего мха, отцветший вереск, рыжие, высохшие полоски нескошенных луговин придавали августовскому пейзажу грустный, нежный и чисто английский оттенок. Тихие, словно отгоревшие в розовом пламени утренние облака на востоке, летающая в воздухе паутина, похолодевшая голубизна озерных вод предвещали скорое наступление ненастья и заморозков.
В письме сыну Штильмарк сообщал, что он «придумал нечто приключенческое, безумно сложное и занимательное, ни в какие ворота не лезущее».
В 1955 году Штильмарка реабилитировали, и он уехал в Москву. Ему удалось передать рукопись Ивану Ефремову, который дал хороший отзыв для издательства «Детгиз». Аллан Ефремов, сын Ивана Антоновича вспоминал: «Отец дал сначала почитать мне и моему другу. Мы прочли взахлёб и высказали свой восторг отцу. Он пробил всё-таки этот приключенческий роман, и тот был в конце концов издан». Роман вышел в 1958 году в серии «Библиотека приключений и научной фантастики» и стал бестселлером. На обложке, кроме Штильмарка, в качестве автора был указан и Василевский. В 1959 году Штильмарк через суд доказал, что он является единственным автором.
Следующая волна интереса к «Наследнику из Калькутты» возникла в конце 1980-х, когда появилось несколько его переизданий и стало возможным рассказать о подлинных обстоятельствах его появления на свет. Сам Штильмарк подробно написал об этом в автобиографическом романе «Горсть света», в котором вывел себя под фамилией Вальдек, а Василевского — под фамилией Василенко.
