Только в августе 1831 года Грейг смог вернуться на Черное море. Здесь у него возникали трения с другими флагманами. По предложению адмирала, 17 февраля 1832 года начальником штаба Черноморского флота был назначен контр-адмирал М. П. Лазарев, однако дела задержали его на Балтике до весны. Летом Лазарев с Грейгом осмотрели восточное побережье Черного моря. Адмирал предоставил предложения о создании Кавказской береговой линии, которую пришлось сооружать уже его преемнику. Лазарев получил представление о сильных и слабых сторонах флота и Севастополя как главной базы. Грейг неоднократно разговаривал с начальником штаба, и тому показалось, что адмирала обуяло равнодушие к службе, вызванное слабой поддержкой Императора и ссорой с Меншиковым.
В октябре 1832 года началась переписка между Грейгом и Меншиковым о подготовке намеченной на следующую кампанию экспедиции в Босфор. На запрос начальника морского штаба Грейг ответил, что можно вооружить 11 кораблей, 7 фрегатов, и указал, что именно необходимо заготовить для вооружения всего флота. Император торопил, чтобы флот был готов и мог выйти в море по первому требованию. Успех египетского паши в боях с турками грозил падением власти султана в Константинополе. Посему следовало отправить суда еще зимой. Меншиков сообщал, что Император, по слабости здоровья Грейга, поручил отправить в море эскадру под флагом Лазарева, но только в том случае, если главный командир сочтет нужным остаться на берегу. Последнее было написано вследствие того, что главный командир 7 ноября сообщал Меншикову, что по состоянию здоровья не может возглавить эскадру.
Через несколько дней прибыла инструкция A. C. Меншикова от 24 ноября 1832 года, в которой была выражена воля Императора приложить старания к вооружению пяти кораблей, четырех фрегатов, нескольких мелких судов и отправить их под командованием Лазарева в Босфор по первому требованию статского советника А. П. Бутенева, посланника в Константинополе. Эскадре следовало защищать турецкую столицу от египетских войск, для чего занять такое положение в проливах, чтобы не допустить египетский флот к Константинополю, а армии не позволить переправиться в Европейскую Турцию. Адмирал отвечал:
«Милостивый государь князь Александр Сергеевич.
С чувством глубочайшего благоволения прочитал я в письме вашей светлости слова Всемилостивейшего снисхождения Его Императорского Величества к слабому моему здоровью, и к крайнему сожалению должен уведомить вас, милостивый государь, что ненадежность состояния оного принуждает меня воспользоваться таковым монаршим снисхождением в представлении другому принять начальство над изготовляемым ныне в кампанию флотом.
Посему, назначая к командованию им контр-адмирала Лазарева, я по крайней мере утешаюсь мыслью, что при настоящем случае служба ничего не потеряет, имея начальником флота адмирала, коего известные до сего опытность, усердие и деятельность ручаются за отличные действия его по возлагаемым на него вновь обязанностям».
10 января главный командир дал Лазареву предписание:
«Вследствие высочайшей Государя Императора воли предлагаю в. пр-ву с получением сего вывести состоящую под начальством вашим эскадру на рейд и содержать оную в таком положении, дабы она по первому повелению могла отправиться в море, производя нижним чинам в числе положенной им морской провизии вместо солонины и сухарей свежее мясо и печеный хлеб».
2 февраля 1833 года первая из трех эскадр под флагом контр-адмирала Лазарева оставила Севастополь и направилась в Константинополь. Успешно выполнив задачу, после заключения Ункияр-Искелесийского договора между Турцией и Россией русские корабли вернулись к своим портам. Вскоре после возвращения Лазарева, доказавшего умение командовать эскадрой, 2 августа 1833 года Император назначил Грейга членом Государственного совета, а Лазарева — временно исполняющим его должность. 31 декабря Лазарева утвердили в должности главного командира Черноморского флота и портов и военного губернатора Николаева и Севастополя.
Еще до нового назначения Грейг оказал стране огромную услугу. В конце июля 1833 года морской министр направил ему на рассмотрение проект соединения всей морской части флота в Севастополе. Адмирал ответил, что проект основан «на ошибочных соображениях сочинителя с упущением из вида самых важных обстоятельств, со вредом государству сопряженных… а потому проект этот в существе своем ничего не обещает, кроме величайших и невознаградимых пожертвований многолетними издержками и попечением правительства, разорением одного из лучших городов в Новороссийском крае с большей частью его жителей, необычных и даже отяготительных для казны расходов на возведение того в Севастополе, что в Николаеве уже существует, на тот только конец, дабы в будущем навсегда увеличить государственный расход и что всего важнее подвергнуть опасности разорения господствующий ныне на Черном море флот наш, со всеми имеющимися теперь способами к возобновлению и поддержанию оного, одним из неотразимых ударов сильного и предприимчивого неприятеля.