Окончив университет в 1837 г. со степенью кандидата, Костомаров определился на службу в Кинбурнский драгунский полк в Острогожске, однако вскоре понял, что военная служба ему чужда. Увлекшись изучением сохранившегося в городе архива уездного суда, Николай задумал писать историю слободских казачьих полков. Оставив полк осенью 1837 г., он вновь приехал в Харьков с намерением пополнить свое историческое образование.
Начался новый период жизненного пути молодого Костомарова. Юноша слушал лекции, штудировал исторические произведения, осмысливал прочитанное. Весну 1838 г. он провел в Москве, посещая лекции в университете и работая в библиотеках. Уже в это время история сделалась для него «любимым до страсти предметом».
Размышления о содержании исторической науки привели Костомарова к мысли о приоритетности истории народа и его духовной жизни перед историей государства. При этом начинать нужно «с изучения своего русского народа, а так как жил тогда в Малороссии… то и решил начать с его малорусской ветви, изучать которую нужно не только по мертвым летописям и запискам, а и в живом народе». Костомаров начал учить украинский язык, перечитал печатную литературу на украинском языке, предпринимал экскурсии из Харькова «по соседним селам и шинкам», слушая народные песни.
Большую роль в его становлении сыграло общение с такими известными литераторами и учеными, как филолог-славист И. Срезневский, украинский поэт и профессор русской истории Харьковского университета П. Гулак-Артемовский, писатель Г. Квитка-Основьяненко, поэт и фольклорист А. Метлинский. Под впечатлением повестей Гоголя Костомаров сам взялся за перо. Уже в 1838 г. он издал под псевдонимом Иеремия Галка свое первое литературное произведение – драму «Савва Чалый», написанную на украинском языке. В следующем году вышел сборник стихов «Украинские баллады», чуть позже – «Ветка». «Любовь к малорусскому слову, – писал Николай Иванович, – более и более увлекала меня; мне было досадно, что такой превосходный язык остается без всякой литературной обработки и, сверх того, подвергается совершенно незаслуженному презрению».
В 1840 г. Николай Костомаров выдержал магистерский экзамен и в 1842 г. напечатал диссертацию «О значении унии в Западной России», которая, однако, в связи с протестом церковных властей и министра просвещения Уварова была снята с защиты, а все экземпляры сожжены. По мнению цензоров, автор слишком отрицательно изобразил духовенство и слишком сочувственно – восстания крестьян и казаков.
Получив разрешение писать диссертацию на другую тему, Костомаров остался верен себе. 13 января 1844 г. ему была присвоена степень магистра исторических наук за защиту диссертации «Об историческом значении русской народной поэзии». Едва окончив ее, молодой ученый приступил к написанию работы о Богдане Хмельницком, ставшей важнейшей в его жизни. Кроме того, он, желая ближе узнать местность, где происходили описываемые им события, определился учителем гимназии – сперва в Ровно, а затем в Киеве (1845 г.).
В 1846 г. Ученый совет Киевского университета единогласно избрал Н.И. Костомарова адъюнкт-профессором кафедры русской истории. Он продолжал работать над книгой о Хмельницком, приготовил и опубликовал извлечения из своих лекций отдельной книгой под названием «Славянская мифология».
В Киеве Николай Иванович сблизился с представителями украинской интеллигенции Н. Гулаком, А. Марковичем, В. Белозерским, П. Кулишом, Т. Шевченко. Вскоре в их среде зародилась и окрепла идея создания общества, целью которого было бы осуществление идей славянского единства на принципах равноправия народов, ликвидации крепостного права, религиозной и социальной свободы. Такой организацией и стало Кирилло-Мефодиевское общество. Костомаров разработал его основные программные положения, изложенные как в «Уставе и правилах», так и в «Книге бытия украинского народа», воззваниях «Братья украинцы», «Братья великороссияне и поляки». В марте 1847 г. Кирилло-Мефодиевское общество в результате доноса подверглось разгрому, ученый в числе других его членов был арестован. После годичного пребывания в Петропавловской крепости при довольно мягком режиме (разрешалось пить чай, курить сигары, читать книги, писать карандашом) Костомаров был отправлен в Саратов в административную ссылку под надзор полиции с запрещением в будущем как преподавания, так и писания произведений. В дорогу он получил 300 рублей, ящик гаванских сигар и право останавливаться в пути, где и сколько захочет. Его матери было выдано профессорское жалование сына за весь срок тюремного заключения. Вскоре она отправилась вслед за Николаем в провинциальный поволжский город.