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