1836–1837 годы Н. провел в ссылке (Усть-Сысольск, Вологда), практически ни на мгновение не оставляя литературного труда (многочисленные статьи для «Энциклопедического лексикона» А. Плюшара, важные работы по истории, в которых Н. явным образом отмежевывается от скептической школы, подведя черту под увлечением идеями Каченовского (см.: «Об исторических трудах в России» // Библиотека для чтения. 1837. Т. 20. Ч. I; «Об исторической истине и достоверности» // Там же. Т. 20. Ч. 2). В 1838 г., отказавшись от приглашения М. А. Максимовича, на ту пору ректора Киевского университета, переехать на Украину для возобновления профессорской деятельности, Н. поселяется в Одессе, где живет до 1842 г., с перерывом на длительное путешествие (1840–1841) по славянским странам Европы (см.: Записка о путешествии по южнославянским странам // Журн. мин. нар. просвещения. 1842. № 6).
В Одессе Н. активно работает в созданном его покровителем, попечителем местного учебного округа Д. М. Княжевичем Обществе истории и древностей, издает два выпуска «Одесского альманаха», где печатает произведения И. И. Лажечникова и И. И. Панаева, В. Г. Бенедиктова и А. Н. Майкова, П. А. Вяземского и М. Ю. Лермонтова, а также собственные очерки «Русская Альгамбра» (о Бахчисарае), «Прогулка по Бессарабии». «Одесский альманах» вызвал сдержанно одобрительный отзыв Белинского, недавнего сотрудника Н., во время пребывания последнего за границей в 1835 г. практически самостоятельно выпускавшего «Телескоп».
Степень и характер влияния Н. на Белинского – один из традиционных пунктов разногласий исследователей. Вопрос осложняется противоречивостью отзывов Белинского о Н., а также прискорбным «хронологическим» парадоксом. Дело в том, что «учитель» пережил собственного «ученика», однако в последние годы совершенно отошел от литературной жизни. Поэтому мнения Белинского, высказывавшиеся «в присутствии» потенциального собеседника, носили односторонний характер, не порождали творческого диалога, приближаясь по своей сути к ретроспективным воспоминаниям. Так или иначе несомненна стилистическая близость к надеждинским работам ранних статей Белинского (особенно «Литературных мечтаний», опубликованных в 1834 г. в «Молве»), а также обоюдная склонность Н. и Белинского к теоретической аргументации, к частому применению в статьях критерия «народности» и др.
В 1837–1842 гг. (и особенно явно в позднейшее время) Н. практически полностью сменил сферу основных занятий, обратившись к истории и этнографии. Столь резкая метаморфоза оценивалась неоднозначно. Так, И. И. Панаев вспоминал, что Н. «при своем замечательном уме вертелся, как флюгер, по прихоти случайностей: без сожаления покидал свое ученое поприще для литературных занятий, литературные занятия для служебной деятельности – и нигде не оставлял по себе глубокого следа» (Панаев И. И. Литературные воспоминания. М., 1988. С. 146; ср. аналогичные мнения С. А. Венгерова, М. М. Филиппова). Однако более взвешенным представляется иной подход. С самого начала взгляды Н. отличались такой степенью теоретической обобщенности, универсальности, что применение их ко всем новым отраслям знания предполагалось как бы само собою. Проект «Телескопа» родился как раз в момент теоретического «расширения» концепции, возникшей в контексте литературной полемики, в область «современного просвещения». И после закрытия журнала Н. оставался верен себе, «основной интерес его все-таки уцелел. Труды Н. направились теперь на научное исследование той народности, которую доселе он защищал как принцип» (Пыпин А. Н. Н. И. Надеждин // Вестник Европы. 1882. № 6. С. 652). Согласно аналогичному мнению, «интересы исторического изучения, отвечавшие сложившейся у него ранее идее исторического самопознания народа, увлекли мысль и пытливость Н. на новый путь» (Данилов В. В. Н. И. Надеждин в Одессе в 1838–1842 гг. // Русский филологический вестник. 1911. Т. 65. № 2. С. 358). Именно понятие народности во всем своем семантическом разнообразии может послужить связующим звеном для выстраивания в единую логическую цепь эстетических и этнографических трудов Н. до и после катастрофы 1836 г.