После назначения на должность Военного Губернатора Николаева и Севастополя Лазарев приступил к благоустройству вверенных городов. Ос-новной перестройке и развитию подвергся город Севастополь. Несмотря на то, что Лазарев имел массу обязанностей как Военный губернатор и Главный командир Черноморского флота и портов, строительство Севастополя он контролировал лично и скрупулезно.
Когда в 1837 году Николай I посетил Севастополь, Лазарев ознакомил царя со своими планами. При непосредственном участии Лазарева был разработан и в 1838 году Высочайше утвержден Генеральный план строительства города. Согласно Плана предусматривалась постройка новых улиц и кварталов, основных объектов: «дом Главного Командира, памятник флигель-адъютанту Казарскому, рядом с которым вместо землянок и негодных строений на сей высоте развести сад, дом для штаба Командира Севастопольского порта, для удобнейшего сообщения между западной и восточной частями города пророется туннель, новый собор в центре города,… дом для полиции с магистратом, пожарною командою и башнею,… дом для Корпуса флотских штурманов, мост и насыпь для сообщения между Артиллерийской слободой и городом, артиллерийский цейхгауз (складское помещение для хранения запасов вооружения, снаряжения, обмундирования, продовольствия – А.Ч.), …вдоль берега Южной и части Артиллерийской бухт планируется каменная набережная» . В основе проекта лежала классическая для русского градостроительства трехлучевая система. Три улицы  - Морская, Екатерининская и дорога на Балаклаву  - соединились в форме буквы «Y». В то время действовал Строительный устав 1832 года, он предусматривал за-стройку в стиле классицизма. Фасады всех зданий оформлялись строго по правилам - крупные здания украшали колоннады и портики, а для небольших обязательным было нечетное количество окон на фасаде с точным соответствием отдельных частей .
То, что Севастополь остро нуждался в перестройке, подтверждают, помимо документов, многочисленные воспоминания современников. Так, англичанин, посетивший Севастополь в начале правления Лазарева, описы-вал его так: «Сам город мало пригоден для проживания. Наилучшая гости-ница на уровне пивной, грязные улицы» .
Со времени основания Севастополя в городе был известен район на центральном городском холме, который получил название «Хребет беззакония». Вот как описывал его в своих воспоминаниях современник: «это лучшая, виднейшая часть местности Севастополя, лежащая против Графской пристани, … в первое время застроена была в беспорядке поставленными и кое-как на обрывистых местах прилепленными лачужками; лачужки с зем-ляными и черепичными крышами, с закопченными и пошатнувшимися стен-ками были гнездилищем жильцов сбродного сословия - мещан, цыган, жен-щин без мужей, чиновников без службы и приюта и в добавок скрыто про-живавших греков и жидов» . Сам М.Лазарев писал: «В Севастополе лучшая часть города, именуемая «Хребет», выходящая к рейдовой бухте и к морю… с давнего времени заселена мелкими частными домиками, хижинами, неправильными, безобразными, без плана улиц и без фасадов. Строения эти … крайне поражают взор бедностью, неопрятностью дворов и неприличием их вида…» . В литературе стало расхожим мнение, что инициатива по сносу «Хребта беззакония» принадлежит Лазареву, однако это не так. Современник Лазарева  Закревский вспоминал, что указание на это дал император Николай I: «В 1837 году, при посещении Севастополя Августейшей фамилией, … Император Николай Павлович, взойдя на Графскую пристань, … взглянув на Хребет беззакония - остановился и, не обращаясь ни к кому спросил: «что это?» Адмирал Лазарев, которому следовало бы отвечать, не придумал ответа на царский вопрос, но капитан 1 ранга Польской, стоя в стороне - ответил: «Хребет беззакония Ваше Величество!» Государь сделал движение рукой, как будто хотел столкнуть лачужки с хребта - сказал, ни к кому не обращаясь: «срыть долой» .
Реконструкция центра началась со сноса застроек на «Хребте беззакония», причем Лазарев настоял, чтобы жителям была выплачена компенсация «во уважение их бедности и для подания возможности выстроить себе новые жилища…» , хотя многие проживали там без всяких законных оснований. Адмирал приказал оценить дома на «Хребте беззакония» и тем, кто имел документы на дома, выплатить по оценочной ведомости. Тем же, у кого таковых документов не было, была оплачена четвертая часть стоимости дома, поскольку это могло бы окупить стоимость переноса дома в другое место.  После сноса трущоб и разбивки участков под общественные здания вся свободная земля Центрального холма отдавалась в частное владение.
На оконечности холма со стороны Екатерининской площади (ныне площадь Нахимова - А.Ч.) в 1838 году был поставлен первый в Севастополе памятник капитан-лейтенанту А.И.Казарскому с надписью «Потомству в пример». Инициатива сооружения этого памятника целиком принадлежит Лазареву. В 1833 году Лазарев, после  смерти Казарского, предложил открыть подписку (т.е. сбор добровольных пожертвований) на установку памятника , и сам первый внес взнос в размере 100 рублей. Здесь же был разбит Мичманский бульвар, для его благоустройства было высажено около 3 тысяч деревьев.
Важнейшей архитектурной доминантой центральной части Севасто-поля является Графская пристань. Она была заложена 14 июня 1783 года в числе первых четырех каменных строений города. В 1787 году к приезду Екатерины II пристань благоустроили и официально назвали Екатеринин-ской. Утвердившееся в дальнейшем название «Графская» ведет начало от командующего Севастопольской эскадрой в 1786-1790 годах графа М.И.Войновича, имевшего обыкновение садиться в шлюпку у этой пристани.
Примечательно, что Лазарев всегда называл пристань по официальному названию - Екатерининская, так как считал, что граф Войнович «никогда не заслуживал, чтобы великолепная эта пристань называлась его именем» , однако название Графская прижилось и сохранилось до нынешнего времени.
На заднем плане памятник А.И.Казарскому и Морская библиотека.
По инициативе М.П.Лазарева в середине 30-х годов XIX века пристань удлинили, построили северную террасу, караульный домик - «каменный домик с одною чистою меблированной комнатой для проезжающих» - и устройство для въезда подвод.
В 30-е годы XIX в. пристани построили каменную лестницу и поста-вили двух каменных львов. В 1837 году М.П.Лазарев решил завершить благоустройство Графской пристани, для чего нужно было удлинить набережную пристани к югу, устроить южную террасу с караульным домиком. Предполагалось также соорудить колоннаду, необходимость строительства которой Лазарев мотивировал желанием прикрыть с рейда беспорядочно разбросанные на площади возле Графской пристани старые здания артиллерийского ведомства и землянки на городском холме, и «чтобы сверх того колоннада эта служила украшением для города и как бы заставой с северной его стороны». По его приказу в 1837 году инженером Д. Уптоном был выполнен проект ее благоустройства .  В следующем году он был представлен Николаю I и был высочайше утвержден за исключением того, что из плана была исключена  колоннадная галерея. Но Лазарев не оставил попыток завершить ансамбль и продолжал обращаться с ходатайством о строительстве колоннады. Был даже использован довод о том, что два извозчика в темноте упали с неогражденой пристани по ступеням. В конце концов Михаил Петрович добился своего. В 1844 году данный проект был утвержден и в течение двух лет реализован . Кроме колоннады, перед лестницей поставили двух новых каменных львов  и четыре статуи (из которых сохранилось две).
Изначально львы были поставлены из мальтийского песчаного камня, но в 1841 году Лазарев через Начальника Главного Морского штаба обратился к императору с просьбой разрешить закупить в Италии мраморных львов, так как старые от непогоды и морских брызг начали осыпаться и «в настоящем виде без крайнего для пристани безобразия оставлены быть не могут» . Разрешение императора было получено. До сегодняшнего дня Графскую пристань украшают львы из каррарского мрамора, созданные итальянским скульптором Фердинандо Пеличчио.
Еще в 1837 году по инициативе Лазарева началось строительство но-вого здания Морской библиотеки. Часть средств на обустройство библиотеки шла из сумм Главного управления флота, а часть была собрана офицерами флота. В 1844 году состоялось открытие новой Морской библиотеки, но через год она была уничтожена пожаром, и Лазарев прило-жил немало усилий для ее восстановления. На восстановление библиотеки царь, по неоднократным просьбам Лазарева, выделил 52 тысячи рублей серебром разделив сумму на три года .  Новая библиотека была заложена в 1846 году, строительство завершили в 1850 году. Когда Лазарев представил императору на утверждение чертеж нового фасада библиотеки, Николай I зачеркнул установленные на парапете статуи в связи с их дороговизной, но несмотря на это, Лазарев решился на заказ и выписку их из Каррары, так как считал, что «без них… здание библиотеки много потеряло бы своей изящности» . Как показывают факты, Лазарев, если считал необходимым,  мог отступать даже от высочайше утвержденных планов.
По инициативе Лазарева в Италии неоднократно заказывались мраморные статуи и барельефы для общественных зданий Севастополя: уже упоминавшиеся скульптуры Графской пристани, два сфинкса, три статуи и два барельефа для Морской библиотеки, две статуи апостолов Петра и Павла для Петропавловского собора, два больших барельефа для Офицерского собрания. Из-за привезенных из-за границы статуй у Лазарева несколько раз случались конфликты с таможней. В своем письме Начальнику главного морского штаба А.С.Меньшикову от 24 февраля 1849 года Лазарев пишет: «Керченский градоначальник (Херхеулидзев) происками своими успел стеснить адмиралтейство наше… и домогался через свое начальство вовсе уничтожить оное… всякий другой, с удовольствием глядел бы на постоянно украшающийся Севастополь; но он, увидев поставленные уже с месяц тому назад на парапете библиотеки статуи, приказал таможенному чиновнику подать себе рапорт о тайном свозе их на берег и воспользовался этим случаем выставить привоз статуй в виде контрабанды…он направил свое донесение министру финансов и с поводу этого присовокупил, что весь южный край России наводняется контрабандою через приходящие из-за границы военные наши суда… Я должен сознаться, что правила при доставке статуй в полной строгости соблюдены не были… позволяю себе надеяться, что Ваша Светлость припишете отступление от правил при свозе статуй на берег скорее к недразумению, нежели к какому либо умыслу провести их тайно, чего и исполнить было невозможно» .  Назначенное Министром финансов расследование окончилось выговором Лазареву за нарушение правил карантинных установлений.
При Лазареве в городе было построено несколько церквей. На цен-тральном городском холме в 1844 году в античном стиле построен собор Петра и Павла по проекту инженер-подпоручика морской строительной части В.А.Рулева, разработанному им в 1837 году .
Находящийся в Севастополе ученик и соратник Лазарева В.А.Корнилов постоянно контролировал проводящиеся в Севастополе работы по строительству, в том числе и по Петропавловскому собору. Он докладывал Лазареву о ходе работ, а также свои предложения по строитель-ству.
Кроме Петропавловского собора была полностью перестроена церковь св. Николая (Адмиралтейский собор) на Екатерининской улице. В 1848 году он был за ветхостью разобран до основания и отстроен вновь, правда, его строительство закончено уже после смерти Лазарева - в 1854 году.  В 1849 году рядом был открыт временный, на время строительства Никольского собора, храм архистратига Михаила . При Лазареве начато строительство Владимирского собора, в котором он и был похоронен.
По инициативе Лазарева в севастопольском городском водопроводе произвели замену глиняных труб чугунными, отлитыми из собранного в чер-номорских портах чугунного лома, что позволило существенно снизить рас-ходы на эксплуатацию водопровода, подсоединить дополнительные источ-ники воды и создать новые линии водотоков .
При Лазареве в Севастополе были проложены шоссе и тротуары по главным улицам .  На момент вступления Лазарева в должность Военного губернатора в Севастополе было всего два казенных учебных заведения, а кроме того, городская буржуазия содержала несколько частных классов и пансионов. В 1833 году в городе открылся первый пансион для благородных девиц . В 40-х годах были открыты уездное и приходское училища, а также морское училище для детей матросов (школа юнг) .
Лазареву удалось добиться постройки нового двухэтажного здания морского госпиталя .  Когда стало известно о целебных свойствах ила Хер-сонесского озера под Севастополем, адмирал постарался использовать «столь драгоценное открытие для облегчения стражду¬щего человечества». Возле озера были поставлены палатки, где работал медик, и несколько боль-ных согласились провести на себе опыт. Результаты опыта показали «необыкновенную пользу... от многих важных из хронического класса болезней, и в особенности от ревматизма». Лазарев обратился к императору с просьбой передать это озеро в ведение севастопольского морского госпиталя, и получил на это высочайшее соизволение. Озеро было передано в ведение морского ведомства и по распоряжению Лазарева начали строиться помещения для больных . Позже Лазарев ходатайствовал перед министром внутренних дел о сооружении на озере грязелечебницы, однако по решению комитета министров было предложено продолжить изучение целебных свойств грязей, а лечебницу  не открывать .
В 1842 году Лазарев обратился к императору с просьбой разрешить построить здание Благородного собрания (также оно носило названия Морского собрания, Собрания флагманов и капитанов, офицерского клуба) на деньги, оставшиеся от «приобретения в последнюю с Турцией войну при-зов», и получил на это высочайшее разрешение . При выборе места для постройки Лазарев в письме от 17 ноября 1842 года обратился  к своему ученику и соратнику В.А.Корнилову, находящемуся в Севастополе с просьбой высказать свое мнение. Корнилов ответил очень быстро и даже прислал наброски здания.
Лазарев контролировал строительство постоянно через Корнилова, Истомина и других доверенных лиц, а также лично в моменты прибытия в Севастополь. В 1844 году, находясь на лечении на Сакских грязях, Лазарев продолжает заниматься проблемами строительства.  В переписке с В.И.Истоминым он просит переговорить с подрядчиками по поводу дверей дома общего собрания, спросить у Акройда чертежи дверей и направить ему на первом транспорте, указывает на необходимость выбрать дерево «самое фигурное, чтобы двери из него вышли самые чудные». В следующем письме он просит Истомина «уведомить меня первым курьером, какие распоряжения Вы сделали на счет ясеневого дерева, - оно очень чудно и двери получились бы самые удивительные…»  .  В 1844 году здание окончено, и в письме Шестакову Лазарев отмечает: «мы из кожи вон лезем, чтобы внутреннее устройство этого здания соответствовало наружнему… давно бы пора устроить такое заведение в Севастополе… оно удалит их (офицеров-А.Ч.) от кондитерских и трактиров; а это не безделица как для нравственности, так и для самой службы…» . 27 июня 1845 года В.А.Корнилов из Севастополя докладывает Лазареву об окончании строительства здания Благородного собрания и тут же о внесенных им изменениях в планировку с приложением схемы.
Однако при строительстве не все шло гладко. В письме Истомину от 1 марта 1846 Лазарев писал: «едва ли удастся клуб открыть прежде исхода этого года, ибо, благодаря тем же инженерам, при первом  дожде  новая  железная крыша всюду потекла, и последствия того были те, что потолок в большой зале, только что живописью искусно оконченный, обвалился и едва не перебил людей, работавших у парка!» .
Однако, когда здание было окончательно построено, очевидцы утверждали, что Благородное собрание Севастополя «… может считаться неос-поримо одним из первых в России» .
Лазарев в случае необходимости мог отступить от любых правил, вплоть до высочайше утвержденных планов, взять на себя ответственность за внесение в планы изменений, но с жестким условием изыскания на это средств без использования казенных денег. Временный в Севастополе Воен-ный Губернатор вице-адмирал Авинов в 1849 году обратился к Лазареву с просьбой внести изменения в высочайше утвержденный в план Севастополя в связи с необходимостью постройки водоотводного канала в Артиллерийской бухте, так как потоки дождевой воды наносят вред зданиям, и Лазарев разрешил внести соответствующие изменения .
В Севастополе  уве¬личилось и число слободок (пригородных селений). К 50-м годам XIX века, кроме существовавших ранее слобод Корабельной, Артиллерийской и Каторжной, возникли еще новые слободки: прилежащие к Артиллерийской—Цыганская, Миллионная, Зеленчужка, Щемелиха и Арсенальная; за западной оборонительной линией —Карантинная,  и между батареями №8 и Александровской — Новая Артиллерийская. Каторжная слободка с увеличением населения утратила свою номинальность и получила название «Южной бухты»; по соседству с  Госпитальной слободкой выросла новая—под названием «Бомборы»; по соседству с  Корабельной слободкой образовалась новая, окружившая подошву и скаты Малахова кургана, под сокращенным названием «Курган»…» . Увеличение количества слободок показывает рост населения Севастополя при Лазареве.
Деятельность Лазарева по строительству Севастополя была высоко оценена современниками. В 50-х годах XIX века современник писал: «Мы в России не имеем ничего похожего на Севастополь. Это не столица, не гу-бернский город и даже не уездный, но он примечен, как сама столица. Улицы широкие, прямые, правильно разбитые, церквей мало, но какие есть - изящ-ные. По улицам  деревья, во дворах сады» . Сам Лазарев писал: «Севасто-поль любимое место, потому что все там сказать мною началось и работ там производится очень много» . А один из английских офицеров в 1855 году, глядя на развалины Севастополя, написал домой: «Ум не может нарисовать себе что-либо равное по красоте тому, чем был этот город. Мне кажется, это место, где любой хотел бы жить и умереть» .
Фактически была произведена перестройка всего города. Лазаревым была заложена концепция развития города, которая во многом определила  его современный вид, а адмирал Лазарев вошел в историю Севастополя  как один из его великих строителей.