Первый приезд Алексея Ивановича в район будущего полигона состоялся в июне 1955 года. В мае он находился на полигоне Капустин Яр, проверял размещение первых подразделений, которые там формировались: батальон связи и испытательные отделы. Там же размещался отдел кадров, который занимался подбором офицеров из состава ГЦП. В этот период Нестеренко внезапно заболел и попал в госпиталь, а через несколько дней на ГЦП прилетел маршал М. И. Неделин в сопровождении генерала Л. М. Гайдукова. К его прилету Алексей Иванович почувствовал себя лучше и прямо из госпиталя выехал на аэродром для следования с маршалом в Тюра-Там. К слову сказать, в период пребывания в госпитале ему удалось уговорить начальника медицинской части госпиталя подполковника медицинской службы А. В. Соловьева дать согласие на должность начальника госпиталя на новом полигоне.
Посадка самолетов была возможной в то время только на аэродроме в Джусалах. Из Джусалов в Тюра-Там группа прибыла в специальном вагоне. Местность и условия расквартирования были удручающими: степь, такыры, солончаки, пески, колючки, жара и ветер, иногда переходящий в песчаные бури, множество сусликов. Ни одного дерева, ни одного населенного пункта. Как сказал адъютант Неделина по приезде на полигон: «Да, это вам не финская баня, это — среднеазиатская пустыня Тюра-Там».
А. И. Нестеренко вспоминал: «Из поселка Джусалы специальной железнодорожной летучкой, состоящей из тепловоза и двух пассажирских купейных вагонов, мы поехали на станцию сосредоточения строителей. Там нашу летучку поставили на временный железнодорожный путь. В металлических, раскаленных солнцем вагонах мы обливались потом и жадно вдыхали воздух, как рыбы, выброшенные на берег. Страшно хотелось пить. Казалось, без привычки невозможно утолить жажду. Чтобы как-то облегчить возможность пребывания в вагонах, где можно было укрыться от палящего солнца, генерал Гайдуков приказал строителям цистерной подвезти воду к вагонам и поливать крыши вагонов водой, особенно ту часть вагона, где находился маршал. Но так как насосов не было, эту процедуру строители выполняли вручную ведрами. Эффект незначительный, но все-таки морально было легче. Тем более что эта примитивная операция производилась под непосредственным руководством генерала Гайдукова».
Только после заката наступала прохлада, которая способствовала быстрому восстановлению сил и энергии. Однако в ночное время одолевали другие неприятности — это надоедливые мухи, комары и москиты, мелкие и кусачие твари. Сколько видно глазам — бескрайняя пустынная степь, покрытая скудной, выжженной солнцем травой. Сама пустыня испещрена такырами, солончаками и кое-где песчаными барханами. Пейзаж пустыни дополнялся множеством сусликов и кругом — ни одного дерева. На станции было только два кирпичных двухэтажных здания и с десяток полуоблупленных глинобитных хибар с плоскими крышами. У некоторых из них стояли юрты. Кое-где можно было видеть исхудалых ишаков да небольшие группки коз или овец. Все это навевало безысходную грусть. Такое первое впечатление испытал каждый прибывающий на полигон.
Самым трудным моментом при подборе кадров для полигона являлось место дислокации. Нельзя было говорить и даже намекать, где оно находится. Чтобы не раскрывать район дислокации, были установлены условные наименования. Основная база полигона, располагавшаяся в Казахстане, называлась «Тайга», база на полуострове Камчатка — «Кама». Многие офицеры, рабочие и служащие, прибывшие в «Тайгу», острили: «Почему же в “Тайге” нет ни одного дерева?»
Когда те, кто давал согласие ехать туда, узнавали, что это в районе Джусалы и Казалинска (в Большой советской энциклопедии он значился как район «природной чумы»), они сразу же отказывались, придумывали всевозможные причины и болезни: колит, гастрит, гипертония, малярия, предрасположенность к туберкулезу, если не у самого себя, то у ближайших родственников — жены, тещи, детей. К тому же требовалась предварительная проверка кандидатов по линии органов безопасности, соответствующая форма допуска. Для оформления допуска каждому офицеру и служащему необходимо было заполнить анкету. Многие вполне подходящие и достойные офицеры, узнав о пустынной местности и особо режимных условиях, отказывались. Приходилось каждому терпеливо и настойчиво объяснять, что эта новая стройка — очень важное мероприятие, в будущем все наладится, но на первых порах придется пережить определенные трудности и т. д.