Дебютировал стихами во фронтовой печати. В 1947 г. опубликовал поэму «Гвардии рядовой», в 1951 г. вышел первый поэтический сборник «Друзьям». Основные темы поэзии Старшинова – война, природа, любовь.

Среди сочинений: поэтические сборники «Веселый пессимист» (1963), «Река любви» (1976), «Милости земли» (1981), «Мои товарищи – солдаты» (1995) и др.; сборник рассказов «Белый камень» (1968); мемуарная проза – «Лица, лики и личины» (1994), «Что было – то было» (1998, посмертно); стихи для детей.

Николай Старшинов составил несколько антологий «Молодые голоса», где собраны более сотни молодых поэтов 1980-х гг. от Бреста до Владивостока. Главный труд Старшинова как составителя – это работа, посвященная 40-летию Победы, работа над составлением 12-томника «Венок славы».

Занимался собиранием частушек, выпустил два сборника.

Николай Старшинов был удостоен Государственной премии РСФСР им. М. Горького (1984).