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