Медаль Нахимова была учреждена 3 марта 1944 года Указом Президиума ВС СССР одновременно с орденами Ушакова и Нахимова. Медаль являлась флотским аналогом «сухопутной» медали «За боевые заслуги», тогда как медаль Ушакова была аналогом медали «За отвагу». Медаль Нахимова предназначалась для награждения за отличия при защите Советского Союза, а также активное содействие успешному выполнению боевых задач частями и кораблями ВМФ и пограничных войск.
Медаль Нахимова была учреждена для награждения младшего состава военно-морского флота. Ей награждались солдаты, матросы, сержанты, старшины, прапорщики и мичманы ВМФ, а также отдельных морских частей погранвойск за инициативные, умелые и отважные действия, которые способствовали успешному решению боевых задач частей и кораблей флота на морских театрах боевых действий. За мужество, которое удалось проявить при защите морских границ Советского Союза. А также за самоотверженность, которая была проявлена при выполнении воинского долга или за другие заслуги, проявленные во время прохождения службы на флоте в условиях, которые были сопряжены с риском для жизни. Медаль Нахимова должна была носиться на левой стороне груди. При наличии других советских медалей она находилась сразу после медали «За боевые заслуги».
Медаль Нахимова изготавливалась полностью из бронзы, форма медали — правильный круг. Медаль окаймлялась бортиком как с лицевой, так и с обратной стороны. На лицевой стороне награды было расположено погрудное изображение адмирала Нахимова в профиль. По окружности в верхней части медали располагалась надпись «Адмирал Нахимов» (все буквы заглавные), в нижней части непосредственно под изображением адмирала располагались пятиконечная звезда и две лавровых ветви. По краям медали находились рельефные точки количеством 110 штук. На оборотной стороне медали Нахимова был изображен парусный корабль, выполненный рельефным. Изображение парусника окаймлялось кольцом из троса. Сам медальон был наложен на 2 перекрещенных якоря. Корабль и якоря дополнительно обрамлялись якорной цепью, которая проходила за якорями. По краю награды с оборотной стороны располагалось 111 рельефных точек.
С помощью кольца и ушка медаль Нахимов крепилась к стандартной пятиугольной наградной колодке, которая обтягивалась синей муаровой лентой из шелка, на которой располагались 3 белых полоски. Белые полоски проходили вдоль ленты и имели ширину в 3 мм каждая. Между белыми полосками были просветы синей ткани шириной по 2 мм, общая ширина шелковой ленты составляла стандартные 24 мм.
Первые медали Нахимова краснофлотцы получили уже 10 апреля 1944 года. Первые вручения наград состоялись на Северном флоте. 10 апреля 1944 года краснофлотцы Ф. Г. Мошков и Е. В. Толстов, а также сержант М. А. Колосов (все три разведчики) получили данную медаль. Первые награждения медалью Нахимова на Черноморском флоте прошли 20 апреля 1944 года. Среди первых награжденных были главный старшина И. Ф. Белкин, старшина 1-й статьи Г. И. Беликов, краснофлотец Н. Д. Белик. На Балтийском флоте первые медали Нахимова были вручены 26 июня 1944 года. Их обладателями стали старшина 1-й статьи В. А. Васильев, а также краснофлотцы П. С. Гаврилов и Н. Г. Вавилкин.
Одним из первых советских моряков, которые были награждены медалью Нахимова, являлся главстаршина Г. М. Давиденко, который пришел служить на Балтийский флот еще в 1936 году по комсомольской путевке. Помимо медали Нахимова, он одним из первых получил и медаль Ушакова. Во время операции по обороне военно-морской базы Балтийского флота, расположенной на территории полуострова Ханко, катер под его командованием 11 раз высаживал десант на занятые финскими солдатами острова. В 1942-1944 годах Давиденко успешно выполнил 121 боевое задание по дозору и конвоированию кораблей, тралению мин. Впоследствии за свои боевые заслуги Г. М. Давиденко был удостоен звания Героя Советского Союза.
В советской истории были и случаи, когда краснофлотцы повторно представлялись к медали Нахимова. К примеру, две данных награды имелось у старшего краснофлотца Мека Ивана Петровича, который служил на одном из торпедных катеров из состава Балтийского флота и был пулеметчиком. Также дважды к данной награде были представлены старшины 2-й статьи С. А. Шевченко и Г. Трофименко. Награждались данной медалью и иностранные граждане. К примеру, 17 июля 1945 года медаль Нахимова была вручена 15 военнослужащим американских ВМС.
Уже после окончания войны прославленный адмирал флота Н. Г. Кузнецов вспоминал, что, бывая на фронтах, он воочию убеждался в том, с какой гордостью краснофлотцы носили свои морские награды. Также ему не раз довелось услышать о том, что награждение медалями Нахимова и Ушакова офицеров флота было знаком высшего отличия, что свидетельствовало об их участии в боях наравне с рядовым составом и об их личном мужестве. Особенно ценили данные награды артиллеристы береговой обороны и морские пехотинцы. Для них награждение медалями Нахимова и Ушакова было свидетельством их принадлежности и причастности к советскому ВМФ, чем моряки всегда гордились вне зависимости от того, где им приходилось служить и воевать — на суше или на море.
В марте 1980 года в статут медали на основании указа Президиума ВС СССР были внесены изменения, которые позволяли награждать отличившихся моряков и в мирное время. К началу 1981 года медалью Нахимова в СССР было награждено более 13 тысяч человек. К моменту распада СССР было произведено более 14 тысяч награждений данной боевой наградой.
