Памятник «Матрос с гранатой» был торжественно открыт 16 сентября 1972 года, к 29-ой годовщине освобождения Новороссийска от немецко-фашистских войск. История появления памятника начинается с 1943 года, именно здесь в страшное время Великой Отечественной войны проходила первая линия обороны, поэтому это место выбрано не просто так. Официально памятник носил ранее название «Матросу-десантнику». 

Его авторами являются два скульптора, которые тоже воевали на фронте - Николай Кириллович Божененко и Николай Иванович Никитин. Памятник выполнен из белого камня высотой в 3 метра и шириной в 4 метра. Именно в городе Новороссийск, памятник матроса - это один из самых больших объектов военной истории.

 Монумент расположен на пересечении проспекта Ленина и бульвара Черняховского. Представляет из себя композицию: небольшая озелененная площадка, на которой стоит монолитный каменный постамент с изображенной фигурой Матроса с гранатой, рядом расположился большой противотанковый еж из металлических рельс.

На высоком постаменте изображен матрос, сжимающий в руках гранату. Его взгляд обращен к следующему памятнику, и так по цепочке от памятника к памятнику, расположенным по всему периметру границы, за которую не удалось прорваться немецко-фашистским войскам. Именно по проспекту Ленина 23 марта 1943 года проходила первая линия обороны города Новороссийск.

На лицевой части памятника, большими золотыми буквами написано: «1943 Здесь проходил передний край обороны «Малой земли»», а с противоположной выбита карта-схема показывающая все линии обороны Новороссийска во время сражений за город, и список подразделений и частей участвующих в этой обороне от немецкой армии захватчиков.

На обратной стороне камня, из которого сделан памятник, размещена карта, на которой отмечены линии обороны и перечень частей и подразделений, которые храбро сражались и защищали город от немецко-фашистских войск.