Николай начал приобщаться к футболу еще во время учебы в коммерческом училище братьев Мансфельд, но поворотным пунктом стало его зачисление в третью команду РГО. Ряд футбольных историков считают, что это произошло в 1917 году, однако дата не увязывается с описанием Андрея, в котором четырехлетняя Вера вместе с другими братьями и сестрой летним утром любуется дома выданной формой: черно-желтой полосатой майкой и белыми трусами. Поскольку самая младшая Старостина родилась в ноябре 1914-го, выходит, речь идет о лете 1919 года? Но здесь, похоже, тот случай, когда поверить надо спартаковской клубной энциклопедии и другим спортивным источникам.
Так или иначе, дебют Николая в тот день не состоялся, хотя сам он к празднику готовился тщательно: начищал бутсы, аккуратно укладывал форму в чемоданчик и даже сидел в погребе, дабы не перегреться на солнце раньше времени. Да и на стадион его сопровождала внушительная группа поддержки — не только братья с сестрами, но и соседские ребята. Однако в состав Старостин не прошел: сочли, что он недостаточно хорошо бегает. Такой вердикт не мог не ударить по самолюбию любого юноши, вот только одних недоверие ломает, а других подстегивает к исправлению недостатков. Николай начал целенаправленно работать над техникой бега и скоростью.
Практически каждый день он тренировал рывки, причем делал это прямо на улицах, лавируя между прохожими. К слову, наличие людей на тротуаре как бы моделировало обстановку на футбольном поле, ведь там тоже приходится обегать защитников. Даже женившись, он не оставил своих занятий и мог изумить Антонину неожиданным спринтом вроде бы в самый неподходящий момент.
Десятилетия спустя, став начальником команды, он рассказывал об этом спартаковским игрокам. В книге Рината Дасаева и Александра Львова «Мы все — одна команда» есть такой фрагмент:
«Николай Старостин, возвращаясь с женой из кино или театра, снимал выходные туфли и в носках делал несколько ускорений по опустевшей в сумерках аллее парка.
— Жалко было время терять, — объяснял он, видя недоумевающие лица тех, кто слушал его впервые. — Если есть настроение, здоровье, то как тут удержишься, чтобы над скоростью не поработать…
Любящий пошутить Гладилин обычно не упускал случая наивно поинтересоваться:
— Так с ботинками в руках и ускорялись?
— Это еще зачем? — искренне удивлялся всякий раз, не чувствуя подвоха, Старостин.
— Ведь туфли пропасть могли. Вы-то побежали, а они стоят беспризорными…
— Почему же беспризорными? А супруга на что? Тут, брат, все рассчитано было».
Упорство на тренировках принесло свои плоды: с годами Николай превратился в скоростного и напористого крайнего нападающего. От представителей этого амплуа в то время требовалось прежде всего убегать от защитников. Но Старостин прибавлял и в других компонентах игры. Когда он работал в мастерских на Ходынке, неподалеку находился стадион МКЛ (Московского клуба лыжников) с футбольным полем. И Николай вместе с Александром и Андреем непременно приходили туда постучать по мячу.
Ежегодным событием в футбольной жизни Москвы тех времен были соревнования на «Приз открытия», проводившиеся сначала перед осенним сезоном, а затем перед весенним. С 1915 по 1922 год они носили имя спортивного деятеля Бориса Майтова, а с 1923-го были посвящены Декабрьскому восстанию 1905 года на Пресне. Команды-участницы сначала набирали зачетные баллы в различных видах программы: обводка препятствий, бег в бутсах на 60 метров, удары по мячу на дальность, эстафетный бег и т. д. После этого очки суммировались, и два лучших коллектива получали право сыграть матч за приз.
Так вот, в 1922-м пара футболистов МКС, составленная из Николая Старостина и Павла Канунникова, показала наилучший результат в пасовке. Суть упражнения заключалась в следующем. Между штрафными площадками обозначался коридор шириной пять метров, в котором устанавливались девять препятствий. Игроки, передавая друг другу мяч, должны были пройти дистанцию как можно быстрее и нанести удар по воротам. Пара уложилась в 18 секунд. В другие годы победители в этой дисциплине не могли выйти из двадцати. О партнере Николая стоит сказать особо: он являлся кумиром всех братьев Старостиных, когда они еще были мальчишками. Когда Канунников приходил к товарищу по команде в домик на Пресненском Валу, тот же Андрей не мог сначала поверить своим глазам, а потом — от восхищения — отвести взор.
Выиграла команда МКС в тот год и эстафетный бег: каждый из одиннадцати спортсменов должен был преодолеть тысячу метров. На это им потребовалось 37 минут 48,5 секунды. Таким образом, можно предположить, что Старостин был неплох не только в спринте, но и на средних дистанциях. Успехи в отдельных дисциплинах позволили футболистам МКС выйти в финал, где они не оставили камня на камне от соперника — команды ЗКС (Замоскворецкий клуб спорта) — 5:1.