За отличие и мужество при обороне Севастополя Григорий Иванович Бутаков был произведён во флигель-адъютанты и награждён орденом Владимира IV степени с бантом.
Севастопольская эпопея послужила для Бутакова боевой школой. Он впервые применил новинки: откренивал пароходы для увеличения угла возвышения орудия, стрелял на ходу по невидимой цели. Но главное — верно оценил значимость и преимущество нового парового флота, на практике в бою применил неизвестные ранее тактические приёмы, приведшие к победе над противником.
Печальным итогом войны 1813–1855 гг. явился запрет России иметь военный флот и базы на Черном море. Век парусных кораблей закончился Синопом. Наступала пора паровых кораблей.
На Черном море среди командиров военных пароходов тогда первенствовал Бутаков. Он же остался единственным из славной плеяды выучеников «лазаревской школы», кого пестовал Лазарев, подобно Корнилову, Нахимову, Истомину. Видимо, всё это учитывал великий князь Константин Николаевич. Новый император спустя четыре дня после вступления на престол уволил А. Меншикова от всех должностей и повелел великому князю Константину Николаевичу, по званию генерал-адмирал, «управлять как флотом, так и Морским министерством».
26 августа 1856 года Г. Бутаков был произведён в контр-адмиралы с назначением в свиту его величества, заведывающим морской частью в Николаеве и военным губернатором в Николаеве и Севастополе.
Бутакову надлежало заботиться о возрождении флота, а о сокращении до минимума остатков прежнего флота.
Началась незнакомая прежде моряку докучная и нудная канцелярская работа. Сокращали береговые учреждения, отправляли в отставку множество офицеров, определяли пенсии, раздавали награды, комиссовали раненых офицеров и нижних чинов…
С первых шагов Бутаков столкнулся с крючкотворством, взяточниками, казнокрадами. На всё это прежде смотрели сквозь пальцы и начальники и чиновная братия. Вскоре Бутаков узнал, что его помощник по интенданту, контр-адмирал Швенднер, замешан в спекуляциях с поставкой военно-морскому ведомству 13 тысяч четвертей гнилой муки. Вместе с ним действовал купец-спекулянт Киреевский и чины управления. Назначенная Бутаковым комиссия изобличила мошенников. Киреевского арестовали, и вскоре в Николаев прибыла из Петербурга «высочайше утверждённая комиссия» во главе с князем Оболенским. Оболенский на словах возмущался и обещал наказать преступников, но конфиденциально посоветовал Бутакову: «Мой совет вам, Григорий Иванович, оставить в забвении проведённое вами следствие…»
Комиссия пригласила в «советники» специалистов-торговцев, которые участвовали в мошенничестве. Вся эта свора постаралась прекратить разбор дела, потому что в нём оказались замешаны лица из Петербурга — подобно обер-интенданту Н. Метлину и другие. С горькой обидой доносил Бутаков рапортом генерал-адмиралу: «Это раскрыло мне, к горькому сожалению, ход, который был дан делу. Зная, что бедное моё отечество подрываемо страшным червём взяточничества, этой повсеместной гангреной нашей, — я выбрал удобный случай, чтобы нанести в пределах вверенного мне управления удар всеобщему врагу…» Бутаков просил, генерал-адмирала об отставке, но тот отказал и неожиданно объявил ему выговор за «неприличную придирчивость и за неисполнение его воли».
С той поры великий князь стал явно недолюбливать Бутакова, а тот в 1859 году представил ему «Секретную записку о положении в Черноморском управлении», в которой дал обстоятельный анализ положения дел в Морском министерстве в целом. По мнению Бутакова, министерство пришло в упадок из-за морального разложения его чиновников. Приведённые в записке факты подтверждали мысль её автора. Бутаков понимал, что он один не в силах вести борьбу с этим злом, а обещанной реальной поддержки не имел. «…Надо же было мне попасть на свою должность в такое время, — восклицает он, — когда всё в России говорило: „Бросьте официальную ложь! Кто же после Севастопольской войны не знает, что у нас сверху блеск, а снизу гниль. Перестаньте молчать об этом…“»