Великий військовий цвинтар біля Костюхнівки був створений після кровопролитної битви 6.11.1915 р., коли польські легіонери відвоювали у росіян пагорб Цегельня, пізніше названий Польською горою. Частина легіонерів - 42 полеглих - була похована на другому цвинтарі, розташованому на Польській горі. Після битви цю територію обнесли колючим дротом і встановили дерев'яний хрест з написом. Цей некрополь, як і інші місця поховань польських легіонерів у цій місцевості, був знищений у комуністичний період.

У 1998 році скаути зі Зґєжського скаутського та гайдівського об'єднання (ZHP) почали відбудовувати це кладовище, роботи були завершені у 2002 році. У наступні роки кладовище перебувало під постійною опікою скаутів. З 2017 року цей догляд фінансується Міністерством культури і національної спадщини в рамках міністерської програми "Місця національної пам'яті за кордоном".