В Одессе Н. активно работает в созданном его покровителем, попечителем местного учебного округа Д. М. Княжевичем Обществе истории и древностей, издает два выпуска «Одесского альманаха», где печатает произведения И. И. Лажечникова и И. И. Панаева, В. Г. Бенедиктова и А. Н. Майкова, П. А. Вяземского и М. Ю. Лермонтова, а также собственные очерки «Русская Альгамбра» (о Бахчисарае), «Прогулка по Бессарабии». «Одесский альманах» вызвал сдержанно одобрительный отзыв Белинского, недавнего сотрудника Н., во время пребывания последнего за границей в 1835 г. практически самостоятельно выпускавшего «Телескоп».
Степень и характер влияния Н. на Белинского – один из традиционных пунктов разногласий исследователей. Вопрос осложняется противоречивостью отзывов Белинского о Н., а также прискорбным «хронологическим» парадоксом. Дело в том, что «учитель» пережил собственного «ученика», однако в последние годы совершенно отошел от литературной жизни. Поэтому мнения Белинского, высказывавшиеся «в присутствии» потенциального собеседника, носили односторонний характер, не порождали творческого диалога, приближаясь по своей сути к ретроспективным воспоминаниям. Так или иначе несомненна стилистическая близость к надеждинским работам ранних статей Белинского (особенно «Литературных мечтаний», опубликованных в 1834 г. в «Молве»), а также обоюдная склонность Н. и Белинского к теоретической аргументации, к частому применению в статьях критерия «народности» и др.
В 1837–1842 гг. (и особенно явно в позднейшее время) Н. практически полностью сменил сферу основных занятий, обратившись к истории и этнографии. Столь резкая метаморфоза оценивалась неоднозначно. Так, И. И. Панаев вспоминал, что Н. «при своем замечательном уме вертелся, как флюгер, по прихоти случайностей: без сожаления покидал свое ученое поприще для литературных занятий, литературные занятия для служебной деятельности – и нигде не оставлял по себе глубокого следа» (