В 1884 г. согласно ходатайству архиепископа Палладия (Раева) Н.Ф. Красносельцев утверждён указом Синода от 18 октября в звании экстраординарного профессора с 31 августа 1884 г. Его заслуги перед наукой были признаны и различными обществами: в 1886 г. Н.Ф. Красносельцева избрали действительным членом Казанского общества археологии и этнографии; в 1887 г. – действительным членом Императорского Московского археологического общества и почётным членом Ростовского музея церковных древностей; в 1888 г. – действительным членом киевского исторического общества Нестора Летописца. В 1888 г., возвращаясь через Одессу из путешествия на Восток, Н.Ф. Красносельцев получил приглашение занять вакантную кафедру церковной истории в Новороссийском университете. Он согласился, надеясь, что это позволит ему чаще посещать библиотеки на Востоке (Научно-исследовательский отдел рукописей Российской государственной библиотеки). 16 марта 1889 г. Н.Ф. Красносельцев был утверждён в звании экстраординарного профессора церковной истории Новороссийского университета. Переход из Казанской духовной академии на новое место службы был связан не только с изменениями условий и места жизни, но и с изменением предмета преподавания, а значит и с расширением научных интересов. Университетская корпорация приняла Н.Ф. Красносельцева хорошо (Научно-исследовательский отдел рукописей Российской государственной библиотеки). Он сблизился с семьёй профессора А.И. Алмазова (Национальный архив Республики Татарстан); очень тёплые отношения сложились у него с Фёдором Ивановичем Успенским и Александром Ивановичем Кирпичниковым (Научно-исследовательский отдел рукописей Российской государственной библиотеки). Основной предмет, который читал Н.Ф. Красносельцев в университете, – церковная история (сохранилась его вступительная лекция). За время преподавания в университете Н.Ф. Красносельцев читал и так называемые специальные курсы: общий курс истории христианской церкви до раскола, спецкурс по истории христианского богослужения за первые шесть веков, который впоследствии был заменён спецкурсом по церковной историографии; спецкурсы «Обзор и критика источников древней церковной истории» и «Обозрение ересей и расколов в Русской Церкви». Придавая большое значение церковной археологии, Н.Ф. Красносельцев не пропустил ни одного археологического съезда: на восьмом Археологическом съезде в Москве в январе 1890 г. сделал доклад, посвящённый русским богослужебным действам XVI–XVII вв. В работе девятого съезда в Вильне в 1893 г. и десятого съезда в Риге в 1896 г. Н.Ф. Красносельцев принял участие как вольнослушатель (Национальный архив Республики Татарстан). 11 декабря 1892 г. он был утверждён почётным членом Казанской духовной академии (Национальный архив Республики Татарстан). В 1893 г. по совокупности учёных заслуг Н.Ф. Красносельцеву была присвоена степень доктора церковной истории (Национальный архив Республики Татарстан). В том же году администрация Новороссийского университета возвела его в звание исполняющего должность ординарного профессора, а в мае 1894 г. его утвердили в этом звании (Национальный архив Республики Татарстан).