Родился в 1901 г. в городе Алатыре Алатырского уезда Симбирской губернии, отец был известным в губернии фотографом. Учился в школе 2-й ступени и в горном училище. В 1920 году мобилизован в РККА, служил пулемётчиком. В том же году был переведён в систему особых отделов ВЧК, где был начальником пулемётной команды. В 1921—1925 гг. служил в особых отделах 4-й Петроградской дивизии, Северо-Кавказского военного округа и 6-й кавалерийской бригады в Бухаре.
В феврале 1921 г. в составе группы чекистов командируется на работу в город Темрюк на Северный Кавказ. В составе опергруппы Особого отдела 9-й армии принимает активное участие в ликвидации банд на Кубани. Затем в качестве помощника начальника особого отделения отдельной кавалерийской бригады участвует в разгроме басмаческих банд в Восточной Бухаре. В 1925—1927 гг. был курсантом Высшей пограничной школы ОГПУ, после окончания которой продолжил службу в особых отделах 9-й Донской кавалерийской дивизии, Северо-Кавказского военного округа и полпредства ОГПУ по Северо-Кавказскому краю. С января 1934 г. — помощник, с июня 1936 г. — заместитель, а с декабря 1936 г. — начальник особого отдела управления государственной безопасности УНКВД Северо-Кавказского (с марта 1937 — Орджоникидзевского) края. В январе 1936 г. Валухин получил звание старшего лейтенанта госбезопасности, а в декабре того же года — капитана госбезопасности. В мае 1937 назначен помощником начальника УНКВД Орджоникидзевского края, а в августе — начальником УНКВД Омской области.
С приходом к руководству Омским Управлением НКВД развернул массовые репрессии в Омском крае, разгромил Омскую партийную организацию во главе с первым секретарем обкома ВКП(б) Дмитрием Александровичем Булатовым.
12 декабря 1937 года трудящиеся Тюменского избирательного округа избрали К.Н.Валухина депутатом Совета Союза Верховного Совета СССР.
В апреле 1938 года решением Политбюро ЦК ВКП(б) Валухин был переведён на партийную работу и назначен 1-м секретарём Свердловского обкома ВКП(б). Проработал в должности меньше года: 30 декабря 1938 г. решением политбюро он был снят с поста «как неоправдавший доверия ЦК ВКП(б)» и некоторое время находился в распоряжении ЦК ВКП(б). В феврале 1939 г. назначен управляющим Калининским свиноводческим трестом, а через три месяца арестован.
9 мая 1940 г. осуждён Военной коллегией Верховного Суда СССР по ст. 58-1 «б», 58-8 и 58-11 УК РСФСР и приговорён к расстрелу. 22 июня 1940 г. расстрелян.
Был женат (жена — Ольга Николаевна Быстрыкова), имел сына. Внучка — драматург Татьяна Валухина.
Брат Николай Николаевич-мл. — также сотрудник органов госбезопасности, зам. начальника следственного управления УНКВД/УМГБ по Краснодарскому краю, майор (1948), награждён двумя орденами Красной Звезды и орденом Отечественной войны. Уволен по болезни в 1950 г.