Приобретя, по сути, статус пехотных частей, балтийские гребные батальоны за короткое время почти утратили связь с флотом. Пополнение шло большей частью из армии, откуда направлялись люди, не имеющие навыков службы на судах. С другой стороны, значительная часть офицерского состава этих батальонов получила подготовку в Морском корпусе и нуждалась в приобретении навыков «солдатского строя». Однако подобная неопределенность длилась недолго: преобразования армии и флота, предпринятые Павлом I, проходили достаточно быстро и решительно. Уже в конце 1796 г. гребные полки возвращаются в морское ведомство, и тогда же императору представляется на утверждение проект очередной реорганизации частей морской пехоты. Проект был одобрен, и в январе 1797 г. гребные полки вновь трансформировались в 4 батальона. Это означало, что, в соответствии со своим гренадерским статусом, гребные батальоны включали 1 флигель-роту, то есть гренадерскую, и 5 фузелерных рот. Местом их дислокации были определены г. Роченсальм (батальоны полковника Демидова и подполковника Бушена) и Петербург (батальоны бригадира Болотникова и подполковника Горожанского). Артиллерийские батальоны генерал-майора Преводелюмиана и бригадира Вильде также направлялись один в Роченсальм, другой в столицу.
В течение 1797 г. комплектовался штат батальонов, определялся порядок их снабжения и содержания. Однако императору Павлу I было угодно уже в начале следующего 1798 г. окончательно решить участь гребной пехоты на Балтике. На сей раз речь шла о ее фактическом упразднении: три первых батальона должны были составить гарнизонный полк в Роченсальме, а батальон Горожанского вливался в гарнизонный полк генерал-майора Беклешова в Кронштадте. На деле из всех этих частей по несколько капральств были определены и в адмиралтейские батальоны.
Иначе при Павле 1 обстояло дело с частями морской пехоты Балтийского корабельного флота. Еще в 1796–1797 гг. разрабатывались проекты реорганизации корабельной пехоты. Предполагалось вновь сформировать морские полки, по численности превышающие пехотные. Они должны были комплектоваться из имевших достаточную выслугу лет нижних чинов армейской пехоты и распределяться по всем кораблям Балтийского флота (его структура с ноября 1796 г. включала 3 дивизии, каждая в составе 3 эскадр). Самыми крупными единицами штата балтийской корабельной пехоты оставили батальоны, и Павел I соизволил привести в штатное расписание 8 флотских и 2 адмиралтейских батальона, на гренадерском положении, то есть по 1 флигель-роте и 5 фузелерных рот в каждом. С учетом общей численности дивизий и эскадр планировалось из рот этих батальонов (по 1 от каждого) сформировать 9-й батальон, что позже и произошло (
Было также определено, что батальоном и его 1-й ротой командует майор, который может быть произведен в старшие чины вплоть до генерал-майора в батальоне же. Кроме того, в батальонный штат включались прапорщики и унтер-офицеры, тогда как музыкантов, наоборот, предписывалось в батальоне не иметь, равно как и шефов. Более того, батальонам не полагались и знамена.
При Екатерине Великой толчок к развитию получил не только Балтийский флот. По мере укрепления южных рубежей России в результате успешных действий в войнах с Османской империей власти обратили внимание и на необходимость создания боеспособного флота на Черном море, тем более что к России был присоединен Крым, строились Херсон, Севастополь, Николаев.
Освоение черноморских берегов и начавшееся здесь «корабельное строение» шло бурными темпами. Руководил работами выдающийся государственный деятель, генерал-фельдмаршал, один из ближайших сподвижников императрицы Г.А. Потемкин, который по праву может считаться основателем Черноморского флота и его морской пехоты.
В Херсоне уже в 1780 г. насчитывалось 180 домов, строились 5 фрегатов и 64-пушечный линейный корабль. Через год там уже стояло 300 домов, в городе дислоцировалось 9 полков.
Тем временем возводились форты и крепости, закладывались новые города. В основанный в 1789 г. Николаев из Херсона были переведены Штаб флота и главные судостроительные верфи.
К 1787 г. Черноморский флот насчитывал 27 линейных кораблей. При установлении его штатов в 1785 г. предписывалось на каждый порт определить по 1 солдатской роте, а для кораблей флота сформировать 3 батальона 4-ротного состава.
Однако для того, чтобы считаться укомплектованным, флот того времени должен был иметь и гребные суда. На Черном море состояние гребной флотилии, в строительстве которой участвовали и греческие мастера, вполне соответствовало требованиям времени. Тем более она находилась под началом помощника Потемкина, умелого администратора, умного, знающего Хосе (Иосифа) де Рибаса, много сделавшего для строительства портов и судов на Черном море.