Вследствие этого повелено было цензора, пропустившего песни, отставить от должности с лишением пенсиона. Цензором был директор саратовской гимназии, который, однако, сумел отписаться и оправдаться. Я думал, что доберутся и до меня, но меня не спрашивали». Как бы то ни было, в отличившийся Саратов был назначен новый полицеймейстер, «отличившийся тем, что на первых же порах, желая угодить начальству, неблагосклонно взглянувшему на песни, ездил по городу с казаком и приказывал бить плетью людей, которых заставал с гармониками поющих песни». А в начале следующего года этот полицеймейстер решил ужесточить режим всех поднадзорных лиц. Однажды он затребовал к себе всех ссыльных и поднадзорных.
«Я был позван в числе прочих, — говорит историк, — и увидел кроме знакомых мне сосланных поляков несколько мужчин и женщин, содержавшихся под надзором не за политические дела, но за всякого рода преступления и проступки. Тут были, как я узнал, и содержательницы домов терпимости, и оставленные в подозрении по разным уголовным делам, между прочим, и по тому еврейскому делу, которое не так давно принесло мне столько неудовольствия. Полицеймейстер, вошедши с грозным начальническим видом, начал читать всем составленные им правила, заключавшие в себе разные наставления о добропорядочном поведении, например: не ходить по кабакам, по зазорным домам, не буянить, не пьянствовать до безобразия и т. п.; но вместе с тем навязывал на всех обязанность не выезжать за городскую черту, ни с кем не сноситься и не вести корреспонденции иначе как с его ведома и разрешения. Прочитавши такое нравоучение, он требовал, чтобы все давали подписку в соблюдении начертанных им правил. Призванные стали подписываться. К удивлению моему, я увидал, что поляки, содержавшиеся по политическим делам, также безропотно подписывались. Когда же очередь дошла до меня, я сказал, что давать такой подписки не стану, потому что хотя я и состою под надзором, но под особым, и по высочайшему повелению определен на службу, в которой я нахожусь».
Дело могло кончиться худо, но Костомаров потребовал, чтобы вопрос был разрешен у губернатора, который к нему благоволил, и вместо того, чтобы наказать историка за дерзкий ответ, губернатор дал ему звание делопроизводителя статистического комитета. Новая должность не мешала ему заниматься историческими изысканиями, он все так же работал с разного рода старинными актами и занялся даже разбором рукописей саратовского собора, некогда отобранных у раскольников. В числе этих рукописей, добавляет с гордостью, он «нашел превосходный и полный список „Стоглава“, самый старейший и самый правильный из всех, какие мне случалось видеть после того».
Скоро ссылка завершилась, и Костомаров вернулся в Петербург. Там он занимался работой над историей Хмельницкого и дополнял новыми выписками из книг и рукописей Публичной библиотеки материалы для «внутреннего быта Древней России» — одной из первых книг в стране, посвященных этой тематике. Режим у него был насыщенный: «С декабря 1855 года я начал ходить в императорскую Публичную библиотеку, занимался печатными источниками в отделении Rossica и рукописями славянскими и польскими. Не проходило дня, в который бы я не сидел в библиотеке, отправляясь туда к десяти часам утра и возвращаясь вечером, обыкновенно в девять часов, если не посвящал вечера на посещение театра. На обед тратил я не более получаса, отправляясь из библиотеки в один из ближайших ресторанов. Так прошло до четырех месяцев. Я почти ни у кого не бывал и погрузился всецело в мир минувшего. Таким образом в этот период моей жизни я успел перечитать множество томов и брошюр по истории Малороссии при Богдане Хмельницком, пересмотрел несколько книг, польских рукописей и перебрал путешественников, писавших о России, из которых сделал себе отметки, относившиеся к чертам нравов и быта, подмеченным путешественниками. В марте 1856 года я отнес экземпляр истории Богдана Хмельницкого к цензору Фрейгангу, как вдруг неожиданно для меня услыхал от него, что при покойном государе состоялось секретное запрещение допускать мои сочинения к напечатанию». Пришлось идти объясняться с Дубельтом, тот запрет снял, книга была напечатана, хотя и пострадала от цензора… Мой «Богдан Хмельницкий», однако, прошел и поступил в распоряжение Краевского, издателя «Отечественных записок». В то же время я поместил статью о «Горе-Злосчастии» в «Современнике»: этот памятник великорусской поэзии XVII века нашел буквально на его глазах в одном из погодинских сборников А. Н. Пыпин.