Nachdem der Lagerfriedhof in Parnewinkel belegt war, suchte die Wehrmacht nach einer neuen Begräbnisstätte. Als geeignet wurde vom staatlichen Gesundheitsamt des damaligen Landkreises Bremervörde eine etwa 2,5 Kilometer vom Stalag X B entfernte Fläche östlich des Dorfes Sandbostel angesehen, "da der Boden in seiner Zusammensetzung genügend luftdurchlässig ist, der Grundwasserstand recht tief und die nächste menschliche Ansiedlung genügend weit entfernt ist (und) auch eine Geruchsbelästigung nicht zu befürchten ist".

Mit Bezug auf dieses Gutachten genehmigte der Regierungspräsident in Stade im Oktober 1940 die Einrichtung des neuen Kriegsgefangenenfriedhofes. Anfang 1941 fanden die ersten Beerdigungen auf dem neu eingerichteten Friedhof statt.

Der Lagerfriedhof war in verschiedene Zonen aufgeteilt. Die verstorbenen Kriegsgefangenen bestattete die Wehrmacht entsprechend ihrer nationalen Zugehörigkeit möglichst nebeneinander liegend in Einzelgräbern. So gab es eigene Gräberfelder für polnische und jugoslawische Kriegsgefangene und ab 1943 auch für italienische Militärinternierte.

Auch die sowjetischen Toten sind in einem gesonderten Bereich bestattet worden, der aber aufgrund der hohen Zahl von Toten ungleich größer war und aus Massengräbern bestand.

Die Bestattung von verstorbenen Kriegsgefangenen war von der Wehrmacht genau geregelt. Während die meisten Kriegsgefangenen das Anrecht auf Einzelgräber hatten, die "in der einfachsten Weise so herzurichten (sind), dass sie als 'Grab' erkennbar sind und bleiben", sollten sowjetische Kriegsgefangene möglichst unauffällig bestattet werden. "Für die (...) Bestattung", so wurde in einem Schnellbrief des Reichsministers des Innern angeordnet,  "ist ein Sarg nicht zu fordern. Die Leiche ist mit starkem Papier (möglichst Öl-, Teer- oder Asphaltpapier) oder sonstigem Material vollständig einzuhüllen." Weiter wurde angeordnet, dass "Feierlichkeiten und Ausschmückungen der Gräber (...) zu unterbleiben" haben und dass die Leichname von sowjetischen Kriegsgefangenen in "Gemeinschaftsgräbern" nebeneinander, aber nicht übereinander bestattet werden sollten.

In der Praxis wurde im Stalag X B aber kaum eine der Anordnungen eingehalten. Die sowjetischen Toten sind meist entkleidet und mit Karren vom Lager zum Friedhof gebracht worden. Dort wurden sie in Massengrabreihen neben-, aber auch übereinander geworfen und verscharrt. Im Laufe des Bestehens des Lagerfriedhofes sollten es insgesamt 70 Massengrabreihen werden, in denen eine bis heute nicht bekannte Anzahl von verstorbenen sowjetischen Soldaten ruhen. 

Die nichtsowjetischen Kriegsgefangenen und die italienischen Militärinternierten wurden gemäß der Genfer Konventionen mit militärischen Ehren und christlichem Ritus in einem schlicht gekennzeichneten Einzelgrab bestattet.

Nach dem Krieg wurden die sterblichen Überreste der Toten aus den westlichen Nationen bis auf wenige Ausnahmen exhumiert und in ihre Heimatländer oder auf andere Friedhöfe in Deutschland umgebettet.