Сам Нахимов писал, что после выхода из дока простоял на рейде без дела полтора месяца, а занял положение брандвахтенного судна с появлением холеры в столице. Он имел дело с 600 судами; из 160 моряков корвета 40 человек заболели и 11 умерли от эпидемии. «Наварин» находился полтора месяца в карантине, после чего 19 июля его направили конвоировать суда. По возвращении три недели судно провело на рейде и вошло в гавань на зимовку.
27 января 1832 года Нахимов удостоился высочайшего благоволения за усердие по прекращению холеры в Кронштадте.
Служба на брандвахтенном судне не удовлетворяла моряка, и он был рад, получив новое назначение. 31 декабря 1831 года приказом начальника Главного морского штаба вице-адмирала A. C. Меншикова П. С. Нахимова определили командиром фрегата «Паллада» с переводом в 4-й флотский экипаж.
«Паллада» имела особое назначение. Николай I хотел построить образцовый фрегат, с использованием усовершенствований, разработанных Комитетом по улучшению флота, в котором активно участвовал М. П. Лазарев. Очевидно, при назначении учли рвение моряка к совершенствованию корвета. 6 мая Нахимову было направлено предписание Кораблестроительного и учетного комитета предоставить ведомость материалов, необходимых для достройки фрегата. Уже 20 мая капитан-лейтенант подготовил требуемую ведомость, а 31 мая предложил дополнительный список усовершенствований.
1 сентября 1832 года фрегат «Паллада» благополучно был спущен на Охтинской верфи. 28 сентября Нахимову вновь было объявлено монаршее благоволение за успешную постройку и спуск фрегата. Усовершенствования командир продолжал вводить и позднее: предложил добавить полубаркас для сбережения баркасов, пушечные станки нового образца и т. п. В мае 1833 года фрегат вступил в строй и был доставлен на камелях из Невы в Кронштадт.
Летом того же года, с 24 июля по 11 октября, фрегат находился в крейсерстве на Балтийском море в составе эскадры вице-адмирала Беллинсгаузена, и вновь Нахимов отличился. 17 августа, в плохую видимость, моряк сумел заметить Дагерордский маяк и дать сигнал, что эскадра идет к опасности. Головной корабль «Арсис» выскочил на камни, получили повреждения корабль «Императрица Александра» и шхуна «Град», но остальные суда успели отвернуть. Нахимов продемонстрировал не только умение, но и мужество, ибо сигнал флагману, что курс его неверен, при ошибке мог стоить моряку карьеры.
Тем временем М. П. Лазарев в 1832 году получил назначение начальником штаба Черноморского флота. К себе он вызывал служить тех моряков, с которыми ходил в плавания и сражение; стал черноморцем и П. С. Нахимов. Качества П. С. Нахимова как морского офицера были столь неоспоримы, что 24 января 1834 года капитан-лейтенанта назначили командовать строящимся линейным кораблем «Силистрия» и перевели в 41-й экипаж Черноморского флота; 30 августа его за отличие по службе произвели в капитаны 2-го ранга. 8 ноября 1834 года начальник Главного морского штаба утвердил Нахимова командиром экипажа и корабля.
В 1834–1836 годах Нахимов занимался постройкой «Силистрии». 11 ноября 1835 года линейный корабль был спущен на воду и его достраивали на плаву. 15 сентября 1836 года корабль вышел из Николаева, зашел в Очаков и 5 октября достиг Севастополя. После завершения вооружения корабль 2 июня 1837 года вышел в первое плавание.
В ходе постройки Нахимов упорно добивался, чтобы «Силистрия» стала образцовым кораблем от киля до клотика. Прочность корпуса и отделка внутренних помещений, современное парусное вооружение и артиллерия выделяли корабль из прочих и позволили ему оставаться одним из лучших в течение двадцати лет — срок, необычный для деревянного корабля.
Но отличный корабль — это не только корпус и мачты. В первую очередь это люди, команда. Подготовке офицеров и матросов капитан 2-го ранга уделял особое внимание. Несмотря на суровые нравы во флоте, которых должен был придерживаться и Нахимов, он уважительно относился к нижним чинам, к нуждам их семей, и потому был любим матросами. Он внушал офицерам: «Пора нам перестать считать себя помещиками, а матросов крепостными людьми. Матрос есть главный двигатель на военном корабле… Вот кого нам надо возвышать, учить, возбуждать в них смелость, геройство. Вот это воспитание и составляет основную задачу нашей жизни, вот чему я посвятил себя, для чего тружусь неустанно, и, видимо, достигаю своей цели — матросы любят и понимают меня…»
От офицеров он требовал не только морской лихости и умения, но и постоянного усовершенствования знаний, сам постоянно следил за новинками прессы и морской литературы.
М. П. Лазарев, ставший в 1833 году главным командиром Черноморского флота и портов, отмечал познания и образованность командира «Силистрии», который служил примером другим морякам и был достоин повышения. A. C. Меншиков 6 декабря 1837 года подписал приказ о производстве командира 41-го экипажа и корабля «Силистрия» в капитаны 1-го ранга. 1 января 1837 года за успешную проводку «Силистрии» из Николаева в Севастополь и 13 сентября за отличное устройство, порядок и чистоту на корабле моряк получил высочайшие благоволения. 22 сентября за отличное усердие и ревностную службу его наградили орденом Святой Анны II степени, украшенной императорской короной.
Усердная служба сказалась на здоровье. 23 марта 1838 года П. С. Нахимова уволили в отпуск за границу по болезни до излечения. Несколько месяцев он провел в Германии, но местные врачи не помогли. Летом 1839 года, после неудачного лечения, моряк по совету Лазарева вернулся в Севастополь; при операции ему повредили нерв ноги в паху, появились обмороки, так что чувствовал себя он хуже, чем до отъезда. Тем не менее Нахимов продолжал службу на море. В 1839 году он не успел участвовать в плавании. Но начиналась продолжительная война на Кавказе. Царское правительство старалось подавить выступления горцев под главенством имама Шамиля за независимость от России. Значительное участие в этих военных действиях принял флот.
В приказе М. П. Лазарева от 4 марта 1840 года о высадке десанта у Туапсе Нахимов был назначен командовать, кроме корабля, гребными судами левого фланга и центра. Главный командир писал Меншикову, что Нахимов играл в высадке главную роль. После занятия Туапсе и Псезуапе Лазарев 19 июня 1840 года охарактеризовал примерную службу капитана 1-го ранга и представил его к ордену Святого Владимира IV степени; но Николай I отклонил представление, сославшись на то, что кампания не завершена.
30 июля — 17 сентября 1840 года, командуя кораблем «Силистрия», Нахимов руководил постановкой мертвых якорей в Цемесской бухте и крейсировал между Анапой и Новороссийском. В октябре он получил высочайшее благоволение за содействие в захвате контрабандистского брига. Но зимой 1841 года Императору донесли о плохо поставленных в Новороссийске якорях. Лазарев 16 января писал Меншикову, что Нахимов в том не виноват, и обещал заменить негодные английские детали. 1 мая — 19 августа 1841 года Павел Степанович ходил из Севастополя в Одессу и Новороссийск и руководил перекладкой и исправлением мертвых якорей в Цемесской бухте.
18 апреля 1842 года за отлично-усердную службу П. С. Нахимова наградили орденом Святого Владимира III степени. Моряк и далее отличался. С 15 июля по 28 августа 1842 года «Силистрия» со второй практической эскадрой находилась в плавании по Черному морю «для практики и эволюции». Командовавший эскадрой контр-адмирал П. Е. Чистяков отметил, что экипаж корабля хорошо сохранял место в строю и исполнял сигналы. Четырежды флагман отмечал «Силистрию» сигналами за соблюдение места в ордере и за скорую перемену парусов. В 1843 году с 14 июня по 5 октября «Силистрия» перевозила из Одессы в Севастополь и обратно войска, а также крейсировала с практической эскадрой, и Чистяков вновь выражал удовольствие за быструю перемену, уборку парусов и спуск фок-реи.
Летом 1843 года вновь команда «Силистрии» проводила установку новых бочек у мертвых якорей в Цемесской бухте. В июле 1844 года корабль Нахимова содействовал войскам, отражавшим нападение горцев на форт Головинский. Узнав 19 июля о нападении, Нахимов подошел к форту, свез на берег десантный отряд и до 26-го числа крейсировал поблизости, пока нападавшие не рассеялись. Начальник черноморской береговой линии генерал-майор барон А. П. Будберг в рапорте Лазареву отмечал, что появление «Силистрии» спасло укрепление от вторичного кровопролитного штурма. За эти действия 30 августа капитан 1-го ранга получил очередное высочайшее благоволение.
В 1845 году, с 1 мая по 15 сентября, Нахимов находился со своим кораблем в плавании по Черному морю, и командовавший эскадрой контр-адмирал М. Н. Станюкович отмечал хороший порядок в соблюдении места и исполнении сигналов, скорую смену парусов. 13 сентября, за отличие по службе, П. С. Нахимова удостоили чина контр-адмирала и назначили командовать 1-й бригадой 4-й флотской дивизии. Начиналась новая служба, теперь в качестве флагмана.