Перед началом строительства необходимо было произвести рекогносцировку районов дислокации, согласовать решения с местными властями об отводе земельных участков, произвести посадку и разбивку объектов. Отводом земельных участков для стартового района, поселка, баз падения отделяемых частей, пунктов радиоуправления полетом ракеты (РУП), измерительных пунктов (ИП), согласованием проектных документов и графиков строительства, подбором кадров, формированием частей и подразделений занимался А. И. Нестеренко. Трудно проходило выделение земельных участков в Казахстане для строительства ИП, РУП, полей падения ступеней. 19 октября 1955 года Нестеренко писал председателю Совета министров Казахской ССР Д. А. Кунаеву: «Постановлением СМ СССР от 29.4.1955 г. и распоряжением СМ Казахской ССР от 18.5.1955 г. Министерству обороны кроме участка 290 000 га по Кзыл-Ординской области должны быть отведены 5 участков по 400 га каждый и 7 участков по 200 га каждый в Актюбинской, Акмолинской, Кзыл-Ординской, Кустанайской и Карагандинской областях». Когда Нестеренко приехал к Кунаеву с документами об отводе участков, тот отказал ему на том основании, что там находятся пастбища для баранов. И только когда Нестеренко обратился к первому секретарю ЦК компартии Казахстана Л. И. Брежневу, которого знал по Черноморской группе войск, вопрос был решен положительно.
Первая группа военных строителей прибыла в Тюра-Там в январе 1955 года.
…Начальник станции Тюра-Там Анатолий Лебедев держал в руках странную телеграмму и никак не мог понять, кто ее подписал. Текст гласил: «12 января проследует литерный, два последних вагона отцепить, поставить в тупик». Поезда останавливаются на маленькой станции всего на две минуты, маневровых паровозов здесь отродясь не было. Как отцепить, чем толкать?
Литерный прибыл точно по расписанию. Гудок паровоза предупредил об остановке. Заскрежетали тормоза, и тяжелый состав замер. Две теплушки отцепили в считаные секунды — помогли молодые ребята, мигом выскочившие из вагонов. Они же, поднапрягшись, столкнули их в тупичок. Руководил ими Игорь Николаевич Денежкин, инженер-строитель. Так он представился начальнику станции.
— А что строить-то будете? — не удержался от вопроса Лебедев.
— Как что? — рассмеялся Денежкин. — Стадион!
(Кстати, до запуска первого космонавта планеты в легендах Министерства обороны и Генерального штаба полигон именовался «стадионом». На самом полигоне «стадионом» называли позже и гигантский котлован, отрытый для первого старта.)
