Monument koło Olsztynka wybudowany został, by upamiętnić zwycięstwo Hindenburga nad rosyjską armią generała Samsonowa w sierpniu 1914 roku.
Środki na jego budowę pochodziły z datków prywatnych. Latem 1924 roku położono kamień węgielny pod jego budowę – dokonał tego sam Hindenburg. W roku 1927 prace budowlane dobiegły końca. Forma architektoniczna budowli przypominać miała w założeniu twórców krąg bloków kamiennych ze Stonehenge, uważany za starogermańskie miejsce kultu. Autorami projektu wybranego przez specjalne jury spośród 381 nadesłanych prac byli berlińscy architekci Walter i Johannes Krügerowie. „Starogermańskim” blokom kamiennym ze Stonehenge odpowiadać miało osiem dwudziestometrowych wież połączonych murami i ustawionych tak, iż całość tworzyła okrąg. Do ich budowy użyto czerwonych cegieł. Materiał ten wywoływać miał skojarzenia z warowniami krzyżackimi. Oprócz tego wykorzystano granit w najróżniejszych barwach. Z kamienia tego wykonane zostały min. herby czternastu miast wschodniopruskich, które najbardziej ucierpiały podczas pierwszej wojny światowej. „Wielką wojnę” upamietniały także poszczególne wieże (wieża sztandarowa, żołnierska i generalska) oraz nisze z tablicai pamiątkowymi, popiersiami i innymi „relikwiami”. Między pobliskim Olsztynkiem a monumentem stębarskim powstał park o powierzchni 7,5 hektara.
Serce monumentu stanowiła krypta, w której pochowano dwudziestu nieznanych żołnierzy. Po śmierci Hindenburga prochy ich przeniesiono do dwóch krypt bocznych, by zwolnić miejsce dla trumien feldmarszałka i jego żony – kryptę tę nazywano od tej pory kryptą Hindenburga. Pogrzeb Hindenburga, prezydenta Rzeszy, w dniu 7 sierpnia 1934 roku przybrał znamiona olbrzymiej manifestacji patriotycznej. W październiku 1935 roku oficjalną nazwę monumentu zmieniono na polecenie Hitlera – z „Nationaldenkmal Tannenberg” na bardziej podniosłą „Reichsehrenmal”. W styczniu 1945 roku wycofujące się wojska niemieckie wysadziły kompleks w powietrze, aby uchronić go przed zbezczeszczeniem przez wroga. Trumny Hindenburga i jego małżonki ewakuowano uprzednio drogą morską na statku „Emden”.