От феодальной зависимости были освобождены около 50 тыс. человек, приписанных к морскому ведомству, постепенно сокращён срок службы нижних чинов на флоте (с 25 до 15, а затем до 10 лет), смягчены правила телесных наказаний нижних чинов (1863 г.). После окончания Крымской войны (1853–1856 гг.) с целью подготовки кадров и сохранения российского присутствия на море Константин Николаевич содействовал возобновлению плавания российских кораблей в Средиземном море (1856 г.), затем – организации кругосветных экспедиций. Своей главной задачей он считал замену парусного флота броненосным и паровым. В целях духовно-нравственного воспитания моряков было начато строительство храмов в местах постоянного базирования русских кораблей за границей, а также устройство церквей на больших кораблях. Так, в 1858–1859 гг. был построен храм во имя святителя Николая и великомученицы Александры в Ницце; рядом, в бухте Вильфранш, стояли русские корабли. В 1852–1855 гг. по инициативе Константина Николаевича был перестроен собор апостола Андрея Первозванного в Кронштадте. Ключарём собора был протоиерей Константин Петрович Несвицкий, бывший благочинный церквей Гдовского уезда Санкт-Петербургской губернии, где находилось имение великого князя. В 1855 г. на дочери К.П. Несвицкого Елизавете Константиновне (1829–1909 гг.) женился священник Иоанн Кронштадтский (Сергиев), который стал клириком Андреевского собора. По условиям Парижского трактата 1856 г. Россия не имела права иметь военный флот на Чёрном море. С целью сохранения кадров военного флота, создания условий развития внешней и внутренней торговли на юге России было создано Российское общество пароходства и торговли. Оно также занималось перевозкой русских паломников на Святую землю. В ноябре 1856 г. Константин Николаевич отправил на Восток чиновника Морского министерства Б.П. Мансурова для написания популярного «Путеводителя ко святым местам». Вернувшись, Б.П. Мансуров представил проект инфраструктуры русского богомолья, который и был взят за основу при создании государственной программы поддержки русского паломничества на Святой земле. В 1858 г. для обсуждения этой программы под председательством Константина Николаевича был создан Палестинский комитет. Путеводитель Б.П. Мансурова был напечатан в 1858 г. в Санкт-Петербурге в типографии Морского министерства под названием «Православные поклонники в Палестине». В 1859 г. Константин Николаевич совершил плавание с русской военной эскадрой по Средиземному морю. В апреле-мае того же года вместе с женой и со старшим сыном Николаем, первым из членов Российского императорского дома, посетил Святую землю, где его сопровождал Иерусалимский патриарх Кирилл II.