18 декабря 1958 г. Указом Президиума Верховного Совета была учреждена медаль «40 лет Вооруженных сил СССР». Рисунок медали был разработан художником В. И. Гоголиным.

Медаль изготавливалась из латуни в виде правильного круга, окаймленного бортиком с лицевой и обратной стороны. На лицевой стороне медали барельеф с погрудным профильным изображением В. И. Ленина. Нижнюю часть медали обрамляет венок из дубовых и лавровых ветвей, на фоне которого расположена рельефная надпись «В ОЗНАМЕНОВАНИЕ СОРОКОВОЙ ГОДОВЩИНЫ», в центре – «ВООРУЖЕННЫХ СИЛ СССР» и дата «1918-1958» и маленькая пятиконечная звезда.

Согласно положению «о юбилейной медали» награждаются все маршалы, генералы, адмиралы, офицеры, старшины, сержанты, солдаты и матросы сверхсрочной службы, состоящие к 23 февраля 1958 года в кадрах Советской армии, Военно-морского флота, войск МВД, войск и органов КГБ при Совете Министров СССР.