Алексей Иванович был находкой для нового небывалого полигона. Подбор кадров облегчала предыдущая должность начальника факультета. Офицеры верили ему и давали согласие ехать вместе с ним на покорение пустыни и космоса. Он также уговорил перейти на новый полигон большую группу офицеров Капустина Яра, что позволило воспользоваться их опытом на новом полигоне. Для формирования также пригодились старые связи и фронтовая дружба: отдельная испытательная станция района падения ГЧ для Камчатки формировалась в НИИ-4, а большинство других служб полигона в Капустином Яре (ранее генерал Вознюк формировал свой полигон в НИИ-4 у Нестеренко, теперь отдал долг). Используя обширные связи, нетрудно было договориться и о подготовке испытателей на предприятиях промышленности, в НИИ и КБ.
На долю А. И. Нестеренко выпал самый тяжелый период в жизни космодрома — проектирование, строительство, формирование, организация испытаний, жизни и быта практически на голом месте в сжатые сроки, когда все небывалые работы надо было делать параллельно. Нестеренко занимался отводом земельных участков для стартового района, поселка, баз падения отделяемых частей, пунктов радиоуправления полетом ракеты (РУП), измерительных пунктов (ИП), согласованием проектных документов и графиков строительства, подбором кадров, формированием частей и подразделений. Трудно проходило выделение земельных участков в Казахстане для строительства ИП, РУП, полей падения ступеней. 19.10.1955 г. Нестеренко писал Председателю Совета Министров Казахской ССР: «Постановлением СМ СССР от 29.4.1955 г. и распоряжением СМ Казахской ССР от 18.5.1955 г. Министерству обороны кроме участка 290 000 га по Кзыл-Ординской области должны быть отведены 5 участков по 400 га каждый и 7 участков по 200 га каждый в Актюбинской, Акмолинской, Кзыл-Ординской, Кустанайской и Карагандинской областях». Когда Нестеренко приехал к Председателю СМ Казахской ССР Д. А. Кунаеву с документами об отводе участков, тот отказал ему на том основании, что там пастбища для баранов. И только когда Нестеренко обратился к Первому секретарю ЦК Компартии Казахстана Л. И. Брежневу, которого знал по Черноморской группе войск, вопрос был решен положительно.
Особенно много хлопот Алексею Ивановичу доставляла база падения ГЧ «Кама» на Камчатке, также создаваемая на голом месте, без надежных коммуникаций, в самом отдаленном, в буквальном смысле медвежьем углу (многочисленные медведи были главным населением этого безлюдного района). Требовалось в кратчайшие сроки, ввиду окончания навигации, согласовать с Министерством морского флота страны состав плавсредств для доставки на Камчатку личного состава, сложной радиотехнической, телеметрической и другой техники, причем разгрузку нужно было производить на рейде без всяких портовых сооружений и средств. В этих работах ему помог командующий Дальневосточным военным округом Маршал Советского Союза Малиновский, под командованием которого Нестеренко воевал на Южном фронте. Нестеренко неоднократно вылетал на Камчатку для личного контроля хода доставки грузов, имущества и спецтехники, контроля строительства и развертывания техники, обустройства личного состава и семей военнослужащих.
Большое внимание он уделял непосредственной связи с НИИ, КБ и предприятиями промышленности, где проходили подготовку офицеры-испытатели. Он осуществлял связь с Генштабом и аппаратом МО по вооружению, решал оргштатные вопросы, занимался главными проблемами перспективного развития Байконура, проявлял недюжинные способности хозяйственника, предвидя и устраняя многие сложности, вызванные недостатками проекта, контактируя с авторами проекта, вникая до мелочей во все вопросы планирования, строительства, быта, обеспечения и культуры.
Трудно было с размещением людей. Жили в спецпоезде, палатках, старых железнодорожных вагонах, землянках, сборно-щитовых бараках, на станциях Тюра-Там и Джусалы снимали комнаты или овчарни у казахов. Трудно было с хлебом, столовыми, баней, прачечной, водой, магазинами, почтой, связью, электроэнергией. Все эти вопросы приходилось решать Нестеренко вместе со своими заместителями.
Алексей Иванович был простым и доступным человеком для всех без исключения, ни капли чванства и высокомерия. Он был контактен и бесконфликтен, хорошо ладил со своими заместителями и начальниками. Опытный организатор, деятельный руководитель, вникающий во все мелочи, влияющие на жизнь и работу подчиненных ему людей. Умелый учитель и воспитатель, он находил нужные слова и ключи к их душам. Требовательный к себе и подчиненным, он умел выслушивать их мнение и использовать рациональное зерно в своей работе. Особенно тепло он относился к молодежи, часто выступал на комсомольских собраниях, встречался со школьниками, солдатами, молодыми офицерами и откликался на все их чаяния и запросы. Его уважали и любили все, кто его знал.
Алексей Иванович был незаурядным человеком. В 1935 г. он возглавил тысячекилометровый пробег на лыжах отряда курсантов Томского артиллерийского училища. Расстояние в 1070 км отряд прошел за 11 ходовых дней. На финиш прибыли без единого отставшего. Этот переход был отмечен приказом Наркома обороны К. Е. Ворошилова. А через две недели Нестеренко участвовал в окружных соревнованиях на лыжах на дистанции 50 км в полном снаряжении со стрельбой на 48-м километре и установил всеармейский рекорд. Он занимался лыжным спортом до самой войны. Кроме лыжного спорта увлекался легкой атлетикой, конным спортом и планеризмом. Сам разносторонне развитый человек, автор книг и художник, мастер спорта по лыжам, он старался благоустроить поселок, быт, обеспечить отдых испытателей после трудной работы. И на полигоне утро офицеров штаба начиналось с физзарядки во главе с Нестеренко.
Несмотря на напряженный труд строителей на основных объектах полигона, уже к 1957 г. были построены купальня на реке Сырдарье, летняя танцплощадка, крытый Летний театр на 600 мест. И сделано было это при его участии и активной работе начальника политотдела В. И. Ильюшенко. В гарнизоне была отличная библиотека, прекрасная самодеятельность, проводились спартакиады и смотры художественной самодеятельности, зеленели первые посадки, превратившие поселок в настоящий оазис, в город-сад, хотя скептики утверждали, что в этой пустыне на солончаках ничего не растет. Алексей Иванович ко всему этому приложил руку и достоин памятника и в истории Байконура и в истории ракетно-космической эры! А что касается мимолетных ошибок, то в сороковые и в начале пятидесятых годов мало кто верил и в ракеты и в завоевание космоса, и даже С. П. Королев, услышав впервые предложения М. К. Тихонравова, усомнился в их осуществлении в ближайшее время. И только приехав к Тихонравову в НИИ-4 и посмотрев его расчеты и графики, он убедился в осуществимости космического полета в ближайшее время с помощью пакетных ракет, созданных из уже существующих ракет. Но Нестеренко за несколько лет до этого, несмотря на недоверие и недовольство начальников, предоставил Тихонравову возможность работать в своем институте над проектом ракеты для полета человека в космос (значит, верил!), добился разрешения для Тихонравова прочитать доклад на научной сессии Академии артиллерийских наук, обеспечил рабочее сотрудничество с Королевым, которое в конце концов привело к созданию первой в мире межконтинентальной ракеты Р-7, первого в мире искусственного спутника Земли.
Я впервые увидел фамилию Нестеренко на обороте своего командировочного предписания, полученного в отделе кадров Министерства обороны на Фрунзенской набережной от известного полковника Чайникова, через которого на полигон прошло целое поколение испытателей. Назначение было настолько секретным, что предписание и билет нам вручили только накануне отъезда. Мы — это 4 выпускника Военной Краснознаменной инженерной академии связи им. С. М. Буденного, авангард контингента из 20 выпускников, отобранных еще за год до этого кадровиком Министерства обороны для неизвестного нам назначения. До этого не говорили, куда нас назначили. В предписании была указана только войсковая часть без места дислокации. И только в железнодорожном билете мы прочли название конечной станции — «Тюра-Там». На обороте предписания едва заметным карандашом было написано: «Хозяйство генерала Нестеренко. Начальник аппаратной машины». Из всего этого я понял, что едем в большую часть (начальник — генерал, и на том спасибо!) и назначен я на должность начальника аппаратной машины, неизвестно, правда, какой. Название «Тюра-Там» нам ничего не говорило, и первым делом мы отправились в книжный магазин и купили географический атлас, где с трудом нашли в Приаральских Каракумах обозначенную самым малым кружком и самым маленьким шрифтом станцию у реки Сырдарья (хорошо, хоть пустыня с рекой!). Поехали на Казанский вокзал узнать, сколько нам ехать до места назначения. Вначале сказали, что поезда на этой станции не останавливаются, потом выяснили, что с недавнего времени некоторые пассажирские поезда останавливаются на 1 минуту, а ехать нам придется трое суток.
