Окончание Крымской войны ознаменовалось для России подписанием в 1856 г. Парижского мирного договора, согласно которому Черное море объявлялось нейтральным, а Россия не могла иметь здесь флот, арсеналы и военные порты. Это заставило рассмотреть вопрос об укреплении берегов Черного и Азовского морей и, в частности, Керченского пролива. Имевшиеся здесь до начала Крымской войны укрепления устарели и уже не соответствовали современным требованиям, потому в том же 1856 г. были проведены исследования местных условий и съемка берегов, после чего было начато проектирование крепости у Керчи для обороны входа в Азовское море, что формально не противоречило статьям Парижского договора. Этими работами непосредственно руководил начальник штаба генерал-инспектора по инженерной части инженер генерал-майор Константин Петрович Кауфман 1-й, направленный в 1857 г. на юг России с задачей усиления обороны Керченского пролива и Днепро-Бугского лимана. Большое внимание этим вопросам уделял также и ставший в 1859 г. директором инженерного департамента военного министерства Эдуард Иванович Тотлебен, герой обороны и создатель укреплений Севастополя.

К концу эпохи гладкоствольной артиллерии дальность эффективного орудийного огня составляла примерно 2 км. Исходя из этого определялись размеры крепостей, и даже относительно небольшие укрепления могли иметь обеспеченное от бомбардировок ядро. Для новой крепости было выбрано место в 4 км южнее Керчи на мысах Павловском и Ак-Бурун и на прилегающих высотах. Расположение укреплений сухопутного фронта крепости, имевшего преимущественно полигональное начертание, выбиралось таким образом, чтобы обеспечить береговые батареи от обстрела с суши. На крепостных верках предполагалось разместить 587 орудий, численность гарнизона была определена в 5235 человек, из них 1860 — артиллеристы. До конца 1856 г. был подготовлен проект, а в следующем году приступили к постройке укреплений, продолжавшейся в течение двадцати лет.

В начале 1857 года в Керчь прибыл первый отряд военных строителей под командованием полковника Ната, приступивший к постройке казарм на мысе Ак-Бурун. Антон Антонович Нат к тому времени был уже опытным военным инженером, шестнадцать лет он прослужил на укреплениях черноморской береговой линии, перестроив и усилив многие из них, за участие в многочисленных боях был награжден орденом св. Станислава 3-й степени и золотым оружием с надписью «За храбрость», но постройка керченских укреплений стала самой масштабной и самой ответственной из порученных ему работ. Кроме инженерно-строительных рот на строительстве крепости были заняты Виленский, Минский и Литовский пехотные полки — ветераны Крымской войны, казаки Кубанского войска и вольнонаемные строители из ближайших губерний. О том, сколь важны были эти работы для России, можно судить хотя бы по тому факту, что финансировались они из отдельного фонда, предназначенного для двух важнейших приморских крепостей империи — Кронштадта и Керчи. Всего на постройку керченских укреплений было израсходовано 12 млн. руб. Император Александр II также уделял этому строительству много внимания. Он трижды побывал здесь, а осматривая в начале 1861 года строящиеся укрепления, он повелел: «В честь трудов, понесённых солдатами… наименовать люнеты, левый Минского, а правый Виленского полка. А главный форт отныне именовать форт Тотлебен». Увиденное столь впечатляло, что после осмотра работ Государь поздравил полковника Ната с производством в генерал-майоры. В 1863 году А. А. Нат был назначен комендантом и командующим войсками керченских укреплений с оставлением в должности их строителя. Через два года, в 1865 году, он получил назначение в Технический комитет Главного Инженерного Управления, а в должности строителя керченских укреплений его сменил Карл Эрикович Седергольм, на долю которого пришлось завершение строительства и приведение крепостных верков в боеготовое состояние. В 1867 году керченские укрепления получили статус крепости, а по завершении строительных работ К. Э. Седергольм стал комендантом крепости Керчь. Во время последней русско-турецкой войны он был начальником обороны восточного побережья Черного моря, а в 1882 году, в чине генерал-лейтенанта, был назначен начальником инженеров финляндского военного округа.