С этих пор он стал жить исключительно на свой заработок и проводить все свободное время осенью, зимой и весной на охоте и экскурсиях, главным образом в окрестностях Оренбурга. Весной, когда начинался пролет птиц, он ухитрялся сбегать пострелять даже в большую перемену между уроками в Зауральскую рощу.
В первые годы молодой учитель старался вписываться в учебный процесс и использовал для более отдаленных поездок только двухмесячные отпуска. В «Послужном списке» за 1880–1883 годы есть записи о том, что он «был в каникулярных отпусках с 1 июня по 5–8 августа».
Об этих первых годах он пишет: «Я бродил по обширным луговым пространствам Илека, по окрестным степям и рощам, я проводил ночи на берегах многочисленных там озер и лиманов, я посещал непролазные топи и болота и всюду наблюдал за деятельностью, неугомонною, бурною жизнью вечно беспокойных птиц, и теперь с каким удовольствием вспоминаю тот свободный воздух, которым дышать мне никто не мог помешать, с какой ясностью возобновляется в моей памяти то высокое чувство свободы и воли, которым я наслаждался, бодро шагая по просторной степи, по барханам и лугам. Много скучных месяцев пройдет моей тусклой, бесцветной учительской деятельности, много раз с тоской буду вспоминать минувшие, настоящей жизнью кипевшие дни, пока опять поведу их так, как привык с давних пор, а не как велят мне другие».
В это время у него уже была большая коллекция птиц, и своей страстью коллекционирования он заразил и некоторых своих товарищей по корпусу. Один из этих сослуживцев тоже собрал порядочную коллекцию птиц, но меньше в них понимал. Случалось, что ему попадался какой-нибудь редкий экземпляр. Тогда Зарудный устраивал мену на какую-нибудь редкость из своей коллекции, а редкость эту приготовлял собственноручно. Например, к туловищу трясогузки пришивал голову овсянки и выдавал это свое произведение за помесь трясогузки с овсянкой. Сослуживец охотно менял свой экземпляр на такую «редкость».
Уже в 1881 году Зарудный публикует первую статью в московском журнале «Природа и Охота» – «Наблюдения над птицами в окрестностях Оренбурга», в которой на 45 страницах приводит данные по 151 виду, главным образом фенологические. Всего за первые четыре года публикует в этом журнале шесть статей, в том числе по содержанию птиц и корсака в неволе. В 1884 году продает коллекцию птиц в Зоологический музей Императорской академии наук, а рукопись монографии «Орнитологическая фауна Оренбургского края» передает профессору М. Н. Богданову, с которым состоял в переписке с 1883 года. Рукопись опубликована в 1888 году, уже после смерти М. Н. Богданова, и вышла под редакцией Ф. Д. Плеске, заведующего в то время орнитологическим отделением Музея. В своём предисловии Ф. Д. Плеске, который также состоял с Зарудным в переписке с 1883 года, пишет: «Описание географического распространения и образа жизни птиц Оренбургского края составлено Н. А. Зарудным превосходно, так что его работа может считаться достойным продолжением и дополнением известного труда покойного проф. Эд. А. Эверсманна «Естественная история Оренбургского края»».
В этой первой большой работе Николая Алексеевича уже вполне сказались характерные черты его последующих фаунистико-биологических трудов – обилие и свежесть фактического материала, наблюдательский и писательский талант, вдумчивое отношение к фактам. Она заняла выдающееся место среди орнито-фаунистических работ и широко использована М. А. Мензбиром в сводке «Птицы России» (1895), где биологические описания ряда видов основаны, главным образом, на данных Зарудного и 15 видов введены в фауну России исключительно на основании его находок. Труд 25-летнего юноши, не имевшего специального биологического образования, научных руководителей и консультантов, изложен на 338 страницах, и по современным требованиям без сомнения являлся бы образцом докторской диссертации.