В апреле 1933 года на страницах газеты «Пионерская правда» появилась «Сказка о военной тайне, Мальчише-Кибальчише и его твердом слове». Затем «Сказка» вышла отдельной книжкой в Детгизе с яркими рисунками художника В. Конашевича.
Целиком повесть была напечатана в 1935 году в журнале «Красная новь» (№ 2) и почти одновременно вышла отдельной книгой в Детгизе.
Как «Сказка», так и повесть в целом вызвала противоречивые оценки критики. Журнал «Детская литература» начал печатать дискуссионные материалы о повести. В январе 1936 г. заведующий отделом культурно-просветительной работы ЦК ВКП(б) А.С. Щербаков, выступая на Всесоюзном совещании детских писателей, сказал:
«Деловой, принципиальный спор, творческая взаимная критика необходимы как воздух. Без этого литература не может развиваться. Плохо то, что иногда идейность и принципиальность в критике подменяются мелкой, ненужной возней, что в эти споры вносятся неделовые моменты, — в результате споры перерастают в мелкие придирки, и тогда грош цена этому спору.
Примером такой непринципиальной, а стало быть, ненужной дискуссии явилась дискуссия о книге Гайдара „Военная тайна“».
Жизнь подтвердила правильность этой точки зрения. «Военная тайна» вошла в золотой фонд советской детской литературы.