Николай Сергеевич еще в юности начал писать стихи, продолжая это занятие всю жизнь, к прозе перешел позднее, к 30-ти годам. Писал прозу «в стол», так как его христианское миропонимание не очень – то соответствовало идеологии советского времени. Писал в свободное от службы время, стараясь ни в чем не отступать от реальных исторических фактов. Его занимали поиски своего индивидуального стиля, «поиски чего-то не избитого, новой метафоры, особого выражения в слове человеческой психологии»(Н. Фудель). Им написаны повести о войне, роман о послевоенном Арбате, цикл исторических повестей о древней Руси. Историческая тематика была у Николая Фуделя реакцией на тяготу современности. Публиковаться начал в 1960-е годы в альманахах «Охотничьи просторы», где вышли в свет его рассказы о природе, о путешествиях по лесам Севера России. В большую литературу Николай Сергеевич вошел повестью «Маршрут Эдуарда Райнера», рекомендованной «Новому миру» Георгием Семеновым и одобренной Владимиром Солоухиным в письме к автору. Повесть была издана в переводах в 10-ти странах: Чехословакии, Польше, Венгрии, Германии и других. Автор получал десятки писем от читателей. Изданная сначала в «Новом мире» в 1983 г. (№ 4) повесть «Маршрут Эдуарда Райнера» входит позднее в первый авторский сборник Николая Фуделя (под псевдонимом Н. Плотников) «Березы в ноябре», вышедший в 1988 г. в издательстве «Советский писатель». Кроме повести, в сборник входят рассказы из «Охотничьих просторов» и рассказы о Киевской Руси. Сборник объединяют психологически точные портреты людей, и природа передает тонкие оттенки чувств и мыслей человека. В 1989 г. в журнале «Родина» публикуется отрывок из исторической повести «Жребий», бывший частью исторического цикла, созданного автором в 60-е годы, – о молодых годах князя Владимира Святославича. В 1991 г. в издательстве «Молодая гвардия» вышел в свет второй сборник Николая Фуделя «С четверга до четверга». «Милосердие, умная гуманность лежат в основе всех сюжетов; некоторые из этих новелл, настолько трогают душу, что по прочтении повести не оставляет странное чувство: неужели это всего лишь слова?..» (Татьяна Толстая).
В 1992 г. в издательстве «Советский писатель» выходит роман «Андрей Курбский», ранее опубликованный в сокращенном варианте в журнале «Москва». На создание романа автора подтолкнуло смутное время 90-ых годов, тема эмиграции, которая в романе приобретает глубоко современное звучание, хотя речь идет о временах Ивана Грозного. В романе поднимаются «те же мучительные и сложнейшие проблемы человеческого бытия, что приходится решать сегодня и нам». (И. Виноградов, из рецензии). Вполне современна и, должно быть, во все времена одинакова мучительная безысходность Курбского, который покинул Родину против воли, спасаясь от гибели, но оказавшись на службе у поляков, вынужден идти против своих же, русских. Брошена жена с маленьким сыном, оставлена Родина. Вынужденное бегство спасло ему жизнь, но оставило кровоточащий разлом в душе, превратив спасенную жизнь в нравственную пытку. Гибель сына, в котором его будущее, не искупить никаким раскаянием. Раздвоенность, оторванность от Родины и муки совести точат и иссушают Курбского. И только в самом конце жизни по бесконечной милости Господней слезами разрешается душа. Описывая духовные искания, нравственные взлеты и падения героя, которые в данной ситуации одинаково свойственны как тому, далекому от нас времени, так и нашему, современному, автор сохраняет «реальный исторический колорит, который был характерен для эпохи Курбского, все те исторические условия, обстановку, ситуации, конфликты, особенности психологии… перед нами подлинный исторический роман, необычайно достоверный во всей своей исторической фактуре» (И. Виноградов, из рецензии). Роман издавался без сокращений в 1995 г. (издательство «Дрофа») и в 1998 г.(издательство «Армада»). В 1996 г. в печати появляется роман «Великий князь Михаил Тверской.14 век. Русь под игом», опубликованный издательством «Сувенир» в Твери. До этого роман 20 лет ходил по самиздату под названием «Иго».