Летом 1858 года, будучи в Петербурге, Николай разыскал Шевченко и увидел его впервые после долгой разлуки. Костомаров нашел его в Академии искусств, где ему дали мастерскую. «И вот однажды после своего обычного купания в Неве, в семь часов утра, зашел я в академию и нашел место проживания Шевченко. Я застал его за работой. „Здравствуй, Тарас!“ – крикнул я, заходя в комнату. Шевченко, отступив шага два назад, удивленно окинул меня взглядом с головы до ног и сказал: „позвольте спросить, кого имею честь видеть?“ – „Неужели не узнаешь?“ – спрашиваю я. „Нет“, – последовал ответ. „Не может быть, – упрямо продолжал я, – присмотрись хорошенько, прислушайся к голосу. Вспомни прошлое! Киев, Петербург, Цепной мост“. Шевченко стал осматривать меня со всех сторон и наконец, пожав плечами, сказал: „Нет, извините, не могу узнать“. Я еще некоторое время заставлял его узнавать меня, однако он, переходя от холодно-вежливого тона к дружески-фамильярному, стал просить не мучить его дальше и назвать себя. Я произнес свою фамилию. Тогда Шевченко, неожиданно для меня, заплакал и дружески обнимал меня и целовал. С того времени в течение двух недель мы виделись ежедневно, особенно вечерами, в трактире, куда я, по договоренности с ним, приходил после окончания своих дневных занятий в публичной библиотеке. В один из таких дней я заметил за нашим уважаемым поэтом такую же выходку запорожской странности, какой показалось мне его громкое пение на улице в Киеве. Договорившись со мной идти к букинисту искать редкую книгу, он прибыл и шел со мной по Невскому проспекту. Одет он был очень бедно, так что фигура его напоминала казака Голоту из народной думы или изгнанного из службы чиновника, который спился и обращается к прохожим с просьбой: „пожертвуйте бедному дворянину“. Что это было своеобразное чудачество, подтверждает то, что ни прежде, ни после Шевченко так не ходил по улицам».
Шевченко, как и раньше, не любил рассказывать подробностей о своей ссылке. Николай Иванович узнал от него только, что сначала ему было хорошо. Потом какой-то начальник дослужился до офицерских чинов из рядовых и стал его притеснять, но к концу службы судьба снова смиловалась: его перевели в Петровское укрепление, где комендант был к нему ласков, приглашал к себе в дом и вообще обращался с ним гуманно. Своим освобождением он считал себя обязанным ходатайству графа Федора Петровича Толстого, который был тогда вице-президентом Академии искусств, и отзывался о нем и его семье с чрезвычайным уважением и любовью.
Через месяц Николай Иванович расстался с Шевченко, выехав в Саратов, куда был приглашен в Комитет по устройству крестьян, а вернувшись в Петербург весной 1859 года, не застал уже там Шевченко: он был отпущен временно на родину.
В 1858 году Совет Казанского университета избрал Костомарова профессором, но Министерство народного просвещения наложило вето на это решение. Труднее для министерства было выступить против решения Совета Петербургского университета, профессором которого Николай Иванович стал в 1859 году. В ноябре Костомаров приступил к чтению лекций по истории России в Петербургском университете. Первым, кто сообщил радостную весть о его утверждении в звании профессора и разрешении читать лекции, был не кто иной, как Т. Шевченко, который вернулся в Петербург в том же году поздней осенью. Первая лекция, посвященная бунту Степана Разина, была прочитана с успехом: 42-летнего профессора студенты на руках донесли к экипажу. Император Николай Павлович так прокомментировал книгу «Бунт Стеньки Разина»: «В Разине нет ничего предосудительного; можете утвердить Костомарова профессором. Но в Киев его пока пускать не следует!»
В следующем году, ознаменованном «Очерками домашней жизни и нравов великорусского народа в XVI и XVII столетиях» («Современник», 1860) и работой «Украинские инородцы. Литовское племя и отношение его к русской истории» («Русское слово», № 5), состоялся публичный спор с академиком М. Погодиным по поводу концепции о роли норманнов в образовании Древнерусского государства. Костомаров отстаивал идею о литовском происхождении первых русских князей (из прибалтийских славян), его оппонент придерживался устоявшегося взгляда на норманнское происхождение первых русских князей и их исключительную роль в образовании государства у восточных славян. Фактически подход Костомарова ниспровергал устоявшуюся к тому времени норманнскую теорию, которая вошла во все учебники как бесспорная.
Вот как об этом вспоминает Николай Иванович: «Старый патриарх русской историографии не мог смириться с моей смелостью и решительностью в вопросе критики устоявшейся к тому времени норманнской теории происхождения русских князей. Он прибыл в Петербург и, встретив меня в Публичной библиотеке, предложил мне вступить в открытый диспут по этому вопросу. Я дал свое согласие, хотя немного поразмыслив, стал сомневаться в необходимости таким образом потешить публику».
