Николай Старостин родился 13(26) февраля в Москве в доходном доме купца Грибова в Большом Харитоньевском переулке (дом № 10), а крещён был 14(27) февраля в храме Харитона Исповедника, что в Огородниках (располагался на месте нынешнего дома № 13 в Большом Харитоньевском пер.).
Детство и юность Старостина прошли в московском районе Пресня, в семье егеря Императорского охотничьего общества, где у них был общий дом с семьей брата отца (адрес: ул. Пресненский Вал, 46; на месте нынешней пристройки к жилому дому с нумерацией № 44), построенный на ссуду Московского общества охоты. О своём происхождении Николай Петрович писал: «Мы были не господские, но и не крестьянские дети. Про нас так и говорили — егерские.»
В 1909 Николай поступил во 2-е Грузинское начальное училище, названное в честь бывшей Грузинской слободе. В 1913 году Николай поступил в Московское училище иностранных торговых корреспондентов Мансфельд (Коммерческое училище братьев Мансфельд), которое располагалось у Никитских Ворот. Учась в коммерческом училище, Николай попробовал впервые играть в футбол.
В 1917 году Старостин приветствовал революцию, хотя и не принимал особого участия в ней.
В 1918 году Николай, окончив училище с отличием, поступил на работу бухгалтером в Центральные ремонтные мастерские Мосземотдела на Ходынке.
15 февраля 1920 года в Погосте от сыпного тифа скончался Пётр Иванович Старостин, отец братьев. После смерти отца Старостин, как самый старший мужской член семьи, поддерживал финансовое состояние своей семьи, играя летом в футбол, а зимой — в хоккей с мячом. В 1920—1921 годах Николай серьезно занимался боксом у тренера Жукова и даже выиграл в полутяжелом весе первенство Москвы среди новичков.
В том же 1920 году Николай был призван на службу адъютантом 9-й Московской военно-инженерной дружины, которая располагалась на Таганке. В 1922 году, отслужив адъютантом, Николай устроился работать заведующим финансовым отделом Московской конторы Нижгубселькредсоюза на Мясницкой.
В 1923 году Николай женился на Антонине Назаровой, которая жила по соседству, в районе Красной Пресни. Ее отец варил квас и содержал квасную.
Никто из братьев Старостиных не мог сказать точно, в какой момент в их жизнь вошел футбол. С 1907 года городская сборная принимала соперников из Санкт-Петербурга, с 1909 уже проходили чемпионаты Москвы по футболу, но тогда это вряд ли еще могло увлечь мальчишек. Возможно, отсчет стоит вести от Олимпиады 1912 года, на которой сборная страны потерпела столь оглушительное поражение (0:16 от сборной Германии), что даже не интересовавшийся футболом дядя Митя отозвался на кухне репликой: «Осрамили Россию, голоштанники!» Но, скорее всего, увлечение началось не раньше 1913 года, с поступлением Николая в коммерческое училище братьев Мансфельд, где игра в мяч уже была популярна. Сам он склонен был говорить даже о 1914 годе.
Приобщение же Николая Петровича к организованному футболу состоялось в 1916—1917 годах с посещения игр первенства города среди учебных заведений, в котором безуспешно участвовала команда коммерческого училища братьев Мансфельд, где учился Старостин. В 1917 году Николай Старостин был зачислен в третью команду по футболу РГО «Сокол». Впервые на настоящее поле Николай вышел весной 1918 года в составе второй команды этого общества в качестве правого инсайда. Поле называлось Горючка, представляло собой известный на всю округу пустырь в Большом Тишинском переулке (примерно на месте современных домов 38с1 и 40к2), где играла команда РГО в 1917—1918 годах.
Весной 1922 года футбольная команда РГО Сокол была переименована в «М.К.С.» (Московский Клуб Спорта), в 1923 году — в «Красную Пресню».
В конце 1930-х годов многие из друзей и окружения Старостина, включая Косарева (22 ноября 1938-го куратор ДСО «Спартак» был снят с должности генерального секретаря, 28 ноября арестован при личном участии Берии, а 23 февраля 1939-го расстрелян), были арестованы в ходе сталинских репрессий.
Также со стороны НКВД были серьёзные попытки контролировать спортивные события. Особо острый конфликт возник из-за полуфинала кубка СССР 1939 года против тбилисского «Динамо», который был переигран после того, как «Спартак» выиграл матч, забив спорный гол. «Спартак» выиграл эту переигровку, которая прошла через 18 дней после финала Кубка СССР, выигранного «Спартаком» у ленинградского «Сталинца», став тем самым единственным случаем в истории футбола, когда после финала вновь игрался полуфинал.
Матч состоялся состоялся 30 сентября и закончился со счетом 3:2. После третьего забитого мяча Берия, по словам Николая Петровича, встал со стула, со злостью швырнул его, вышел из ложи и уехал со стадиона. А 27 октября, забив три безответных мяча тбилисцам уже в чемпионате страны, «Спартак» практически гарантировал себе 1-е место. Тбилисское «Динамо» в итоге заняло 2-е место. Судьба Старостиных была предрешена. Николай Старостин, по его собственным словам, в 1939 году ждал ареста каждый день.
После начала войны перед спортивными обществами были поставлены задачи военного времени. На базе в Тарасовке, по согласованию с Мосгорвоенкоматом, были сразу организованы группы подготовки призывников, где молодежь обучали штыковому бою, метанию гранат, плаванию, лыжному спорту, борьбе, боксу. Началась и подготовка снайперов. Рядом с Тарасовкой, в Подлипках, находилось несколько заводов, выпускавших продукцию военного профиля. Николаю удалось добиться согласия городских властей, чтобы команду «Спартак» почти в полном составе зачислили на завод. Предприятия, на которых работали братья, были перепрофилированы на производство продукции для военных нужд.
Так дни проходили в череде нескончаемых забот, Николаю Старостину приходилось постоянно что-то «утрясать» и согласовывать, колесить по городу, безуспешно пытаясь оказаться сразу в нескольких местах. А ночью, как и многие, Николай Петрович дежурил на крышах, наловчившись под руководством дворника Пахомыча тушить вражеские «зажигалки». Закончилась страшная зима 1941/42 года. И хотя никто тогда, не мог знать, сколько продлится война, Старостиным казалось, что худшие времена позади.
Но как раз к концу зимы с Николая, Александра и Андрея негласно сняли звания заслуженных мастеров спорта. И это было еще не всё. По утрам на работу Николая отвозила служебная машина, и как-то раз его водитель обратил внимание на практически неприкрытую слежку. Автомобиль с двумя мужчинами в одинаковых шляпах сопровождал их автомобиль и припарковался неподалеку от конторы. Старостин отреагировал дерзко: подошел к преследователям и предложил им передать начальству, что для встречи с ним необязательно кататься по всему городу.
Последний финансовый документ, подписанный Николаем Старостиным в должности руководителя МГС «Спартак», датирован 19 марта 1942 года. 20 марта 1942 года Николаю удалось вернуться с работы раньше обычного. Ночью Николай Петрович был арестован. Той же ночью в 4 часа утра были арестованы Андрей и Пётр. Чуть позже взяли мужей сестер — Петра Попова и Павла Тикстона (28 марта), близких друзей-спартаковцев — бухгалтера планового отдела ДСО «Спартак» Евгения Архангельского и Станислава Леуту (21 августа), а также других функционеров ДСО «Спартак» — заместителя председателя общества Анатолия Денисова (18 сентября), начальника снабжения Исаака Ратнера (28 октября) и Александра Сысоева.
18-20 октября 1943 года Военная коллегия Верховного суда СССР вынесла братьям Николаю, Александру, Андрею и Петру приговор: 10 лет лагерей, поражение в политических правах на 5 лет и конфискация всего лично им принадлежащего имущества. Николай по этапу направлен в Ухту, Александр — в Пермь, Андрей — в Норильск, Пётр — в Нижний Тагил. Остальным, проходящим по «делу Старостиных» был определен срок заключения в 8 лет содержания в исправительно-трудовых лагерях с аналогичными дополнениями. Павел Тикстон осужден был раньше, получил наказание в 10 лет лагерей и поражение в политических правах на 3 года. Петр Попов был освобожден и отправился добровольцем на фронт.
В 1950 году Николай Старостин, отбыв 8 из 10 лет, досрочно был освобожден. Директор одного из местных заводов Рябов когда-то работал инженером в Москве, жил на Красной Пресне, болел за «Спартак». В 1948 году он придумал хитрую комбинацию, пробив зачисление политического заключенного на предприятие и его допуск к работе на станке. За выполнение дневного плана со срока списывалось 2-е суток. А фактически на этом станке точил болванки осужденный из Иркутска Дмитрий Михалев, пока его напарник уходил на тренировки. В свою очередь, Николай Петрович, пользуясь свободой передвижения, оказывал благодетелю разные услуги, принося из города то, что нельзя было купить в лагерном магазине. Так прошли 2 года, которые были зачтены Старостину за четыре. Местный народный суд утвердил досрочное освобождение, однако поражение в правах оставалось в силе. Выпущен был Старостин с формулировкой «-16» (запрещено жить в 16 центральных городах СССР). Восстановить московскую прописку возможности не было, а перевозить семью в Хабаровск, где предлагали тренировать «Динамо», не хотелось. Но Старостину не пришлось делать самостоятельный выбор: последовал новый звонок от Василия Сталина, который пообещал уладить вопрос с переездом в столицу.
После смерти Сталина и последующего свержения и уничтожения Берии Хрущёвым все притеснения братьев Старостиных со стороны властей были объявлены незаконными, и братья были освобождены. Андрей Старостин был приглашён на должность начальника сборной СССР по футболу, Александр стал председателем Федерации футбола РСФСР, а Николай в 1955 году был приглашён на должность главы спортивного общества «Спартак» — эту должность он занимал вплоть до 1992 года.
1 февраля 1992 года Николай Старостин вместе с Олегом Романцевым, а также с армейцами Павлом Садыриным и Виктором Мурашко, динамовцами Валерием Газзаевым и Николаем Толстых, торпедовцами Евгением Скомороховым и Юрием Золотовым выступили с меморандумом, в котором заявляли об отказе от участия в чемпионате СНГ по футболу — новообразовании, которым предполагалось заменить чемпионат СССР.
Николай Петрович Старостин скончался 17 февраля 1996 года на 94-м году жизни. Похоронен в Москве на Ваганьковском кладбище. Могила расположена на Центральной аллее некрополя. Ранее на том же кладбище были похоронены его братья.
