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