В 1835 г. были закончены работы по кладке фундаментов и стен казематов на Александровской батарее. Но других каменных работ на приморских укреплениях по разным причинам в том году не выполняли, что вызвало недовольство Николая I. Строитель Севастопольской крепости был снят и вместо него назначен инженер-полковник Фалькерзам.
В 1836 г. Фалькерзам начал строительство Константиновской батареи. В плане укрепление повторяло очертания берега мыса и имело форму подковы. Правый фас укрепления обстреливал акваторию перед рейдом, центральная закругленная часть — вход в бухту, левая назначалась для поражения прорвавшихся на рейд кораблей противника. В двух ярусах размещалось 54 каземата, а над ними платформа для открытой обороны. На этой батарее было обеспечено постоянное присутствие артиллерийской прислуги в казематах. Каземат длиной 12 м разделялся сквозным проходом на орудийную и жилую части. В последней устанавливали нары и печи в круглых железных футлярах (печи в любое время года обеспечивали положительную температуру для проживающих в казематах солдат). Горжевую часть защищали ров и две оборонительные казармы. Они соединялись при помощи двух стен с казематами, образуя замкнутую, удобную для обороны территорию. Казармы предполагалось построить по типовому проекту на 250 солдат каждая, с кухнями, пекарнями и складами. На флангах казематов находились трехэтажные, хорошо защищенные пороховые погреба, а во внутреннем дворе — большая металлическая емкость для запаса воды. Защитники такого укрепления могли выдержать длительную осаду десанта противника.
В конце 1834 г. командиром Черноморского флота и портов, военным губернатором Севастополя и Николаева назначается вице-адмирал М. П. Лазарев. Бесстрашный флотоводец, мореплаватель, первооткрыватель Антарктиды, талантливый администратор, М. П. Лазарев видел свой долг в самоотверженном служении Отечеству, соблюдении справедливости и чести. Уважительное, заботливое и одновременно требовательное отношение Лазарева к подчиненным, личный пример мужества, организованности и трудолюбия повседневно воспитывали моряков. Его последователями стали сотни офицеров и адмиралов. Среди них имена В. А. Корнилова, П. С. Нахимова и В. И. Истомина, которые с гордостью называли себя учениками Лазарева. Волею судеб после кончины их навечно соединил могильный склеп во Владимирском соборе Севастополя.
Михаил Петрович Лазарев (1788 — 1851) окончил в 1803 г. Морской кадетский корпус в Санкт-Петербурге. Он принимал участие в русско-шведской войне 1808—1809 гг. и Отечественной войне 1812 г. Будучи командиром судна "Суворов", в 1813—1816 гг. совершил кругосветное плавание, во время которого открыл атолл, получивший название «Суворов». В 1819—1821 гг., командуя шлюпом "Мирный", Лазарев участвовал в экспедиции Ф. Ф. Беллинсгаузена, первой побывавшей у берегов Антарктиды. В 1822—1825 гг. в кругосветном походе на фрегате "Крейсер" М. П. Лазарев провел ряд научных исследований по метеорологии, океанографии и другим прикладным наукам. Имя М. П. Лазарева увековечено в названиях многих океанских островов и бухт; моря, ледника и научной станции в Антарктиде; порта в Японском море и арктического ледокола. В 1826 г. капитан I ранга Лазарев, в то время командир линейного корабля "Азов" и начальник штаба русской эскадры, отличился в Наваринском сражении. За умелое руководство боем и личное мужество Лазареву было присвоено звание контр-адмирала. Во время русско-турецкой войны 1828—1829 гг. контр-адмирал Лазарев возглавил эскадру, блокировавшую Босфор и Дарданеллы.
Командуя в течение 18 лет Черноморским флотом, адмирал Лазарев сделал очень многое для его развития. Под его руководством было построено 16 линейных и свыше 150 других судов, среди них первые пароходофрегаты* и корабли с железным корпусом. Часть флота получила на вооружение бомбические пушки**. Обладая широким кругозором, М. П. Лазарев понимал, что корабли, береговая база, укрепления и город, составляющие единое целое, способны решать стратегические задачи государства, поэтому много времени и сил уделял вопросам строительства. В 1832 г. контр-адмирал Лазарев направляет доклад начальнику Главного морского штаба князю А. С. Меншикову, в котором сообщает, что нормальное проживание моряков и размещение новых экипажей в Севастополе обеспечить невозможно. С помощью влиятельного князя (князь А. С. Меншиков, праправнук царского сподвижника А. Д. Меншикова, был возвышен и приближен Николаем I — праправнуком Петра I) М. П. Лазарев добился разрешения на строительство казарменного городка, и в 1834 г. началось возведение современных трехэтажных зданий, украсивших город. После Крымской войны перед разрушенным фасадом одной из "лазаревских" казарм был сооружен памятник замечательному флотоводцу и созидателю[37]. По предложению вице-адмирала Лазарева начинает строиться новое Адмиралтейство и пять сухих доков. К ним прокладывается в пробитых через горы тоннелях и возведенных над балками акведуках водопровод от Черной речки.
В 1838 г. командир Черноморского флота обратился в Главный морской штаб с рапортом о реконструкции и развитии Севастополя. В 1840 г. был утвержден генеральный план города и началось его осуществление. Моряки сносили трущобы на городском холме, прокладывали бульвары, разбивали скверы. При активном участии М. П. Лазарева была основана морская библиотека, возведены Петропавловский собор, здание морского собрания, реконструирована Екатерининская (Графская) пристань. По настоянию Лазарева архитектурный облик городских сооружений выдерживался в строгом классическом стиле.
На объектах, предназначенных для Морского ведомства, командир Черноморского флота имел возможность постоянно влиять на состояние работ. По его приказанию в помощь строителям выделялись моряки и баржи для перевозки строительных материалов; он вел контроль за качеством и сроками строительства зданий. Что касается возведения фортификационных сооружений, то оно всецело находилось под опекой Военного министерства, которое ревниво оберегало свою епархию от вмешательства моряков. Конечно, моряки допускались к обсуждению проектов, но участие в строительном процессе было полностью исключено. Вице-адмирал Лазарев в таких случаях прибегал к испытанному методу. Тщательно изучив состояние строительных дел на батареях и бастионах, он направлял подробный рапорт в Главный морской штаб. Минуя Военное ведомство, без "сглаживания острых углов", доклад с соответствующими комментариями доводился до Николая I. Одно из таких донесений поступило вместе с отчетом Инженерного департамента о строительстве в Севастопольской крепости за 1835 г. В нем сообщалось о недопустимо медленном развертывании работ по утвержденному императором плану, несмотря на растущее напряжение в отношениях с Турцией[38]. Это заставило царя принять неординарное решение по ускорению реконструкции крепости. Военный министр 2 апреля 1836 г. сообщил Инженерному департаменту, что на Севастопольских укреплениях Николай I повелел в 1837 г. выполнить строительных работ на один миллион рублей. Таким образом, по сравнению с предыдущим годом надлежало увеличить темпы строительства более чем в десять раз. Немедленно последовало соответствующее приказание Строителю Севастопольской крепости инженер-полковнику Фелькерзаму, одновременно ему направили распределение означенной суммы по отдельным сооружениям. Согласно этому документу, следовало завершить Александровское укрепление, выполнив все работы на сумму 156 тысяч рублей; по Константиновской батарее — закончить всю каменную кладку и освоить 344 тысячи рублей. Далее расходы разбивались следующим образом: по восьмой батарее — 130, четвертой батарее — 100, по четвертому и пятому бастионам — 190 тысяч рублей; так называемые издержки производства составили 80 тысяч рублей.