В состав лагерного сбора входили подразделения самых разнообразных родов войск Красной Армии: пехотинцы, кавалеристы, танкисты, артиллеристы, связисты, вплоть до ОДОН — отдельной дивизии особого назначения. Футбол проник всюду и везде стирал в ходе спортивной борьбы всякие грани субординации — и среди участвующих, и среди зрителей».
В армии Андрей Петрович вступил в партию. После демобилизации он вернулся к своей прежней жизни — игра в футбол и хоккей, учеба, ипподром… В 1930 году он познакомится с Ольгой Кононовой, известной в ту пору цыганской актрисой. Их брак будет официально заключен почти через 20 лет.
Андрей вернулся из армии окрепшим и возмужавшим. Вырос на четыре сантиметра, а объем грудной клетки увеличился аж на восемь. При этом в его игре сохранялись легкость, изящность. Вот как писал об Андрее Старостине известный в тридцатые годы журналист Алексей Холчев: «Его на поле я помню не только хорошо, но и более осознанно. Андрей Старостин был одной из самых ярких и колоритных фигур в отечественном футболе. Убежден, что первый же взгляд на футбольное поле выделял среди участников именно его. Он как бы притягивал к себе внимание зрителя. Играл он при системе „пять в линию“ центрхава, а после освоения „дубль-вэ“ — центрального защитника. Широкоплечий, могучий, с копной черных волос, постоянно спадавших на лоб, в полинявшей рубашке и светлых бутсах, он всегда находился в гуще событий. Казалось, что все нити находятся у него, а сам он — полновластный командующий на поле. Было слышно, как он покрикивал на своих товарищей, и те безоговорочно выполняли указания. Игра Андрея Старостина была сродни грозной всевластной стихии. Он словно стоял в одном ряду с былинными русскими богатырями. Были в нем их исполинская стать, и залихватская удаль, и беззаветная смелость, и первозданная мужская красота. Я уже упоминал, что играл он в застиранной рубашке. Андрей Петрович, как и большинство великих спортсменов, был суеверен и терпеть не мог что-то менять в своей футбольной жизни».
Постепенно Андрей Старостин превратился в ведущего игрока команды «Спартак». Обратимся к воспоминаниям известного журналиста Льва Филатова: «Вот он остановился чуть позади раскинувшихся веером пяти форвардов, это его место на поле, центрхава, центра полузащиты. Ноги широко расставлены, плечи наклонены вперед, черные волосы взъерошены, сбиты набок, и он не спешит их поправить. Кажется, что это по его воле идет атака, он ею управляет, от него игра расходится лучами. Я помню его зычное, басистое, на весь динамовский стадион: „Володя, играть будете?!“ Так он взывал к форвардам через их лидера, правого инсайда Владимира Степанова. Если, по его мнению, форварды прохлаждались, он вставал, уперев руки в бока, живым укором. Но не жалостным, вымаливающим, а властным, карающим. Легко было представить, что товарищам совестно оглянуться, что они боятся попасть под испепеляющий взгляд».
Так уж получилось, что к учреждению чемпионата СССР в 1936 году Николай Старостин как игрок сошел со сцены — на счету Николая Петровича всего одна встреча в первенстве страны. Сходил с футбольной сцены и Александр Старостин. Травма колена сломала футбольную карьеру младшего из братьев, Петра. И в первых чемпионатах страны Андрею Старостину приходилось порой в одиночку отстаивать честь знаменитого клана. Три раза Андрей Петрович становился чемпионом Советского Союза в составе довоенного «Спартака», дважды брал Кубок. Будучи игроком сборной СССР, он выезжал на товарищеские матчи в Европу. Но главным событием в жизни довоенного советского футбола стал приезд сборной Страны Басков летом 1936 года.
Это турне имело не только спортивный (а в составе баскской сборной было немало замечательных профессионалов, игроков сборной Испании, призеров чемпионата мира), но и политический характер. Ведь баски представляли собой ту часть Испании, что героически сражалась в гражданской войне против Франко.
Самым ярким в серии был матч басков со «Спартаком», усиленным несколькими известными футболистами. В этой встрече именитые профессионалы потерпели поражение со счетом 2:6. Андрей Петрович был непосредственным участником матча.
«И они приехали. Вот они идут по перрону Белорусского вокзала. Уверенной, чуть развинченной походкой ковбоев, знающих себе цену. Идут как бывалые, поездившие по миру парни, себя показавшие и других посмотревшие. Не глазеют по сторонам, как новобранцы туристической группы, а присматриваются привычным глазом к незнакомой толпе встречающих. Толпа огромная, на всю привокзальную площадь. Истины ради оговоримся, что в то время она была значительно меньше. На месте памятника Горькому стояли дома. А рядом была трамвайная станция, тоже занимавшая изрядное место на площади.
Интерес к приезду басков определялся количеством заявок, поступивших в дирекцию стадиона „Динамо“. Желающих попасть на первую встречу с „Локомотивом“ оказалось два миллиона человек.