Медаль учреждена 7 апреля 1998 года Постоянным Президиумом Съезда народных депутатов СССР. Награждались ей моряки – ветераны войны, адмиралы, офицеры, мичманы и матросы, а также военнослужащие действительной военной морской службы и сотрудники научного потенциала, связанные с проектированием и созданием военно-морских объектов.
Адмирал Флота Советского Союза, Герой Советского Союза Николай Герасимович Кузнецов родился в 1904 году в деревне Медведки Котласского района Архангельской области.
В 1919 году 15-летний Николай вступил в Северо-Двинскую военную речную флотилию, приписав себе два года, чтобы быть принятым. В 1926 году закончил Военно-морское училище имени М.В.Фрунзе. На Черноморском флоте служил командиром батареи, командиром роты, старшим вахтенным начальником.
С 1929 по 1932 год Кузнецов учится в Военно-морской академии и с отличием оканчивает ее. После учебы его назначают старшим помощником командира крейсера «Красный Кавказ». Благодаря его деятельности в 1933 году крейсер вошел в состав боевого ядра Черноморского флота.
С ноября 1933 по август 1936 Кузнецов командовал крейсером «Червона Украина», где довёл до совершенства систему боевой готовности одиночного корабля. Позднее она была принята на всех флотах СССР. В 1935 году «Червона Украина» заняла первое место в Морских Силах РККА. За успехи в организации боевой подготовки крейсера в том же году Кузнецов был награжден орденом «Знак Почета».
К началу Великой Отечественной войны Николай Герасимович внёс существенный вклад в повышение боеготовности сил и средств ВМФ. Накануне нападения Германии на СССР принял меры по повышению боеготовности флотов, а в ночь на 22 июня отдал приказ о приведении их в полную боевую готовность, что позволило избежать потерь кораблей и морской авиации.
31 мая 1944 года Кузнецову присвоено воинское звание адмирал флота. 25 мая 1945 года это звание приравнено к званию Маршала Советского Союза и введены погоны маршальского типа. 14 сентября 1945 года Кузнецов получил звание Героя Советского Союза.
