Постройка памятника началась в 1993 году, а закончилась 9 мая 1996года. Автором проекта является Олег Владимирович Ковальчук. При изготовлении памятника применялись различные материалы. Колонны, символизирующие стойкость солдат, выполнены из черного лабрадорита. Для основы использован гранит. Арки сделаны из стали. Колокол, олицетворяющий вечную память погибшим, отлит из бронзы. Его строительство вели АОЗТ "Арсити" и венгерская фирма "Генерал". Изготовлением арок занималось ЦБПО-4. Колокол доставили из Москвы.

Заказчиком выступила администрация города Нижневартовска и общественное объединение "Красная звезда". Итальянская фирма "Тегола-Канадезе" оказала благотворительную помощь в поставке гранита и лабрадорита на облицовку памятника.