Осенью 1922-го форварда Московского кружка спорта включили в состав сборной Москвы. Кандидатуры для участия в товарищеском матче со сборной Петрограда обсуждались на заседании Московской футбольной лиги. Когда заместитель ее руководителя Николай Гюбиев предложил включить Старостина, за Николая проголосовали шесть участников заседания из одиннадцати, то есть большинство. Домой, по словам самого Старостина, он вернулся крайне взволнованным, даже Александра Степановна это сразу заметила. Младшие братья и вовсе были поражены таким поворотом в его карьере. Петроградцам москвичи уступили, но Старостин забил гол и получил хорошую прессу. В дальнейшем цвета сборной Москвы он защищал вплоть до 1935 года.
В 1923-м, когда место МКС заняла «Красная Пресня», она тоже выиграла эстафету, хотя в других показателях не преуспела. А в 1924-м на обложке номера 9/10 журнала «Красный спорт» появилось фото Николая, разрывающего грудью финишную ленточку, с подписью: «Приз им. „Декабрьского восстания Красной Пресни“. Победа Кр. Пресни в эстафете 11 х 1000 метров. Финиш Старостина». В отчете ему был уделен отдельный кусок: «Последний этап Райкомвод (Холин I) начинает метров на 30 впереди от Красной Пресни (Старостин). Уже на втором кругу (каждый этап равнялся 4 кругам по 250 метров) Старостин достает Холина, вместе с которым они оказываются далеко впереди остальных. Холин заметно сдал, но Старостин, который выглядит совершенно свежим, не торопится его обходить и проходит, сберегая силы для финиша, целый круг сзади него. На последнем кругу резким броском Старостин обходит противника, легко отрывается от него и, прекрасно финишируя, дает красивую победу своей команде». А вот в пасовке они с Канунниковым в тот раз допустили техническую ошибку, и «Красная Пресня» в этом упражнении поделила последнее место.
Много лет спустя Андрей в шутку описывал Льву Филатову игру старшего брата: «Николай был ярчайшим представителем стиля „бури и натиска“. Представьте, бежит он по правому флангу с мячом, и на пути его вырастает защитник. Что, вы думаете, предпринимает Николай? Он берет защитника за шиворот, пользуясь своей немалой силой, переносит его на беговую дорожку и бежит дальше к воротам…»
Более серьезно, но в похожих красках отзывался о нем Петр: «Это ж сущий дьявол был! Скорость, напор, жажда борьбы невероятные. Удержать его ох как трудно было».
Зимой поддерживать форму Николаю помогал русский хоккей. На льду он тоже действовал в нападении, становился чемпионом Москвы в 1927-м и 1928-м, РСФСР — в 1932-м и 1934-м, СССР — в 1933-м. Участвовал в Международной рабочей спартакиаде 1928 года в Норвегии, где сборная СССР не знала себе равных, причем в ее состав входили как раз временно переквалифицировавшиеся футболисты.
Быть может, на зеленом поле на фоне иных технарей Старостин действительно смотрелся несколько прямолинейно. Но ведь не зря же он в течение четырнадцати сезонов входил в сборную Москвы, включался в сборную РСФСР, а чемпионом РСФСР был четыре раза: в 1922, 1927, 1928 и 1931 годах. На его счету шесть неофициальных (то есть не вошедших в реестр ФИФА) матчей за сборную СССР. Бывал Николай ее капитаном, забил один гол — в ворота Турции в 1933-м на московском стадионе «Динамо». Константин Есенин писал о той встрече: «По ходу игры турки реализовали два штрафных, данных турецким судьей Кемалем Халим-беем, Николаю Старостину с подачи Петра Дементьева удалось отквитать только один гол».
Сам Николай Петрович рассказывал о себе так: «За мяч я всегда боролся горячо и, чего скрывать, вратарям покоя не давал. Шел на столкновения с ними, как говорят, „действовал в тело“». Однажды после матча Ленинград — Москва он зарубился на словах со своим старым товарищем, известным вратарем Николаем Соколовым, и пообещал ему, что в следующий раз не будет щадить лежащего голкипера и перепрыгивать через него. Однако остыл и впоследствии не выходил за рамки дозволенного. Да и с ним самим оппоненты порой не церемонились. Андрею Петровичу запомнилась игра в столице Австрии между сборными Вены и Москвы: «Мощного сложения австрийский вратарь вывел из игры бросками в ноги троих наших игроков. У бровки поля лежал с поврежденным голеностопом Николай Старостин…» У болельщиков он имел прозвище Апень (от слова «аппендицит» — потому что во время игры часто держался за правый бок).
К дисциплине старший брат относился очень щепетильно и долго не мог забыть случая, когда сам же ее нарушил. Как-то раз жена приболела, и он взял на игру пятилетнюю дочку Женю. Усадил ее на стул рядом с воротами, которые сам же собирался атаковать, рассудив, что и за ребенком сможет наблюдать краем глаза и девочка будет постоянно видеть отца где-то поблизости. Но в какой-то момент малышка выскочила на поле навстречу отцу. Судья остановил игру свистком, сорвав опасную атаку команды Старостина…