Родился 8 февраля 1919 года в деревне Климино (ныне Сернурский район Марийской Республики). Рано остался без родителей, воспитывался в детском доме (город Уржум Кировской области). Окончил 8 классов, работал на кожевенной фабрике в Казани и одновременно учился в аэроклубе. С 25 мая 1939 года в рядах Красной Армии, служил красноармейцем в 227-м конвойном полку Внутренних Войск НКВД СССР на Украине.

С июня 1941 года в действующей армии (Юго-Западный и Западный фронты). 15 августа 1941 года тяжело ранен и контужен. Дальше плен, побег. Раненого бойца приютила простая женщина Евдокия Антиповна Леоненко. Она подлечила его и показала дорогу к своим. 7 ноября 1941 года Н. В. Новосёлову удалось пересечь линию фронта. Его направили долечиваться в госпиталь. Выздоровев, подал рапорт о переводе в авиацию. Просьба была удовлетворена, в конце января 1942 года он прибыл в 16-й запасной авиационный полк. Летал на У-2, вскоре назначен командиром звена управления. Летом 1942 года освоил истребитель Як-1, работал лётчиком-инструктором, окончил курсы командиров звеньев.

С 10 сентября 1943 года лейтенант К. В. Новосёлов сражался в составе 115-го Гвардейского ИАП, летал на Як-9 и Як-3. Воевал на 1-м Прибалтийском, 3-м Белорусском и 1-м Украинском фронтах.

К 9 маю 1945 года заместитель командира, он же штурман эскадрильи 115-го Гвардейского истребительного авиационного полка (7-я Гвардейская истребительная авиационная дивизия, 2-й истребительный авиационный корпус, 2-я Воздушная армия, 1-й Украинский фронт) Гвардии старший лейтенант К. В. Новосёлов совершил около 150 боевых вылетов, провёл более 30 воздушных боёв, в которых сбил лично 13 самолётов противника (в последнем наградном листе от 5 мая 1945 года говорится о 12 личных и 5 групповых победах) и в паре 1 аэростат наблюдения. Войну закончил в Берлине. 1 мая 1945 года участвовал в сбрасывании с самолёта флага Победы над рейхстагом. Указом Президиума Верховного Совета СССР от 27 июня 1945 года удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (№ 6519).

После войны продолжал служить в ВВС. В июле 1952 года заместитель командира по лётной подготовке 224-го ИАП (32-я ИАД) прибыл в Северный Китай и с сентября 1952 года по июль 1953 года принимал участие в Корейской войне. Летал на МиГ-15, воздушных побед не имел. 11 октября 1952 года сбит в воздушном бою. При катапультировании приземлился на горно-лесистую местность, получил множественные переломы и травмы. 7 июля 1953 года Гвардии подполковник К. В. Новосёлов уволен в запас по болезни. Жил в городе Ворошиловград (ныне Луганск). Умер 20 марта 1985 года.

Награждён орденами: Ленина (27.06.1945), Красного Знамени (08.08.1944, 06.09.1944), Отечественной войны 1-й степени (30.04.1945); медалями.