Родился в крестьянской семье. Окончил Пундужскую семилетку в 1927 году, работал счетоводом и культармейцем по ликвидации неграмотности. В ноябре 1933 года был призван в Красную армию, там учился в полковой оперативной школе войск НКВД, а затем работал помощником командира взвода 12-го кавалерийского полка войск НКВД. После демобилизации Николай Евгеньевич первое время работал нотариусом, а затем получил должность народного следователя Харовской районной прокуратуры. В 1937 году окончил трехмесячные юридические курсы в г. Архангельске.

      Во время Финской кампании Николай Евгенье­вич вновь был призван, работал секретарем, а затем военным следователем 56-й стрелковой дивизии. В августе 1940 года он вернулся домой и вновь был назначен народным следователем в районную прокуратуру. Однако и года не прошло, как Николаю Наташову вновь пришлось оставить свое место.

      23 июня 1941 года он был мобилизован, работал сначала военным следователем 111-й стрелковой дивизии, а затем военным прокурором. В июле 1942 года он был демобилизован и почти сразу получил должность в областной прокуратуре. Во время войны Николай Евгеньевич работал прокурором отдела по надзору за милицией, прокурором следственного отдела прокуратуры области. В мае 1950 года был назначен помощником прокурора по спецделам. После изменения структуры аппарата прокуратуры области Наташов становится помощником прокурора области по надзору за следствием в органах госбезопасности. В феврале 1973 года Николай Евгеньевич вышел на пенсию.

       Ветеран прокуратуры Запечин Лев Александрович вспоминает, что с Николаем Наташовым дружили семьями, так как он тоже Харовчанин. Несмотря на то, что определенный период времени Николай Евгеньевич был прокурором по спецделам, он был очень доброжелательным, контактным человеком. Прокурор по спецделам — это очень тяжелая ноша для человека, так как ему приходилось присутствовать при приведении приговора в исполнение, то есть при расстреле осужденного. Не каждый человек мог без ущерба для своей психики выдерживать такое испытание годами.

   Николай Наташов был награжден Почетной грамотой прокурора области, Почетной грамотой Областного комитета профсоюза работников госучреждений и прокуратуры области. Ему неоднократно объявлялись благодарности, в том числе и от Генеральной прокуратуры СССР, за его добросовестный труд.