Родился 26 февраля 1902 г. в Москве.
В 1918 г. с отличием окончил коммерческое училище братьев Мансфельд (Москва). В 1918-1920 гг. работал бухгалтером в Центральных ремонтных мастерских Московского губернского земельного отдела. В начале 1920-х гг. служил адъютантом 9-й Московской военно-инженерной дружины.
В 1922 г. Николай Старостин стал заведующим финансовым отделом московской конторы Нижегородского губернского союза сельскохозяйственных и кредитных кооперативов. В середине 1920-х гг. возглавлял секцию спорттоваров, работавшую в структуре Московского союза потребительских обществ.
Николай Старостин начал играть в футбол в 1918 г. в команде Русского гимнастического общества (РГО). Позиция - нападающий. В 1922 г. представлял футбольный клуб "Московский кружок спорта" (МКС), который в 1923 г. перешел под управление Краснопресненского райкома комсомола и получил название "Красная Пресня" (в дальнейшем на протяжении 1920-1930-х гг. этот клуб выступал под названиями "Пищевики" и "Промкооперация"). В 1920-1930-х гг. Николай Старостин также входил в сборные Москвы и РСФСР. На протяжении этих лет неоднократно становился победителем и призером первенств Москвы, РСФСР и Советского Союза. В 1932-1934 гг. провел несколько неофициальных матчей за сборную СССР.
22 сентября 1934 г. было объявлено о создании добровольного спортивного общества (ДСО) "Спартак". Его задачей являлось привлечение к занятиям физической культурой и спортом работников артелей промысловой кооперации, а также членов их семей.
Идея названия общества принадлежала Николаю Старостину: он предложил назвать его именем Спартака – римского гладиатора, предводителя восстания рабов против Римской
республики в I веке до н. э. Старостин также придумал эмблему - красный ромб, пересеченный по диагонали белой полосой, с буквой "С" в центре.
14 ноября 1934 г. появилось сообщение о переименовании футбольного клуба "Промкооперация" в "Спартак".
19 апреля 1935 г. Всесоюзный совет физической культуры при Центральном исполнительном комитете СССР утвердил устав ДСО "Спартак", проекты формы, флага и герба. В 1935-1942 гг. Николай Старостин возглавлял Московский городской совет общества "Спартак".
В марте 1942 г. Николай Старостин и три его младших брата, футболисты-спартаковцы Александр (1903-1981), Андрей (1906-1987) и Петр (1909-1993), были арестованы сотрудниками НКВД. В октябре 1943 г. их приговорили к десяти годам исправительно-трудовых лагерей за антисоветскую агитацию, взятки и хищения. В 1945-1950 гг. Николай Старостин, отбывая срок в различных лагерях, тренировал заключенных. В первой половине 1950-х гг. проживал в ссылке в Казахской ССР (ныне Республика Казахстан). Его младшие братья отбыли срок целиком. В 1955 г. дело Старостиных было пересмотрено, всех их реабилитировали.
В 1955-1964, 1967-1975 и 1977-1995 гг. Николай Старостин был начальником московского футбольного клуба "Спартак".
В 1980-х гг. - председатель Совета ветеранов спартаковцев г. Москвы.
В 1991-1996 гг. являлся почетным президентом Международного физкультурно- спортивного общества "Спартак".
Автор книг "Звезды большого футбола" (1967), "Мои футбольные годы" (1986), "Футбол сквозь годы" (1989).
Николай Старостин скончался 17 февраля 1996 г. в Москве на 94-м году жизни. Похоронен на Ваганьковском кладбище.
Герой Социалистического Труда (1990).
Заслуженный мастер спорта СССР (1934).
Николай Старостин был награжден орденами Ленина (1937, 1987, 1990), Дружбы народов (1982), "За заслуги перед Отечеством" III степени (1995).
Был женат на Антонине Петровне Старостиной. Дочери - Евгения и Елена.