Während des Ersten Weltkriegs kämpften an der Mazedonischen Front etwa 30.000 deutsche Soldaten und Offiziere, von denen einige fielen und an verschiedenen Orten bestattet wurden. Nach dem Krieg zeigte der deutsche Staat Interesse daran, die sterblichen Überreste seiner Soldaten zu sammeln und in einem Massengrab oder einem Ehrenbeinsheim beizusetzen, dessen Gestaltung den Kulttraditionen der deutschen Geschichte entsprechen sollte.
Laut erhaltenen Archivdokumenten beantragte die deutsche Regierung im Mai 1930 ein Grundstück in Bitola für ein Ehrenbeinsheim für die im Ersten Weltkrieg in Bitola und Umgebung gefallenen deutschen Soldaten.
Der deutsche Soldatenfriedhof in Bitola wurde auf einem Hügel in 1050 Metern Höhe im Nordwesten der Stadt errichtet.
Der Friedhof ist unter verschiedenen Namen bekannt: Totenborg, Deutsche Festung der Toten in Bitola, Deutsches Ehrendenkmal in Bitola. Unter den Bürgern ist die Bezeichnung „Deutscher Friedhof“ am gebräuchlichsten.
Totenborg wurde in über einem Jahr erbaut und ist ein architektonisches Werk des berühmten deutschen Architekten Robert Tischler. Der Bau erfolgte unter der direkten Aufsicht des Deutschen Volksbundes für die Pflege der Kriegsgräberstätten.
Die Beschreibung und das Modell von Totenborg wurden erstmals in den „Neuen Bauplänen des Volksbundes“, Nr. 83–85, veröffentlicht, was die Urheberschaft des Architekten Robert Tischler und den Planungsbeginn (1929/30) eindeutig belegt. Die Bauarbeiten begannen 1934, die Einweihung fand am 25. Oktober 1936 statt. Nach der Fertigstellung von Totenborg wurde der Sarkophag in die Mitte der Gedenkhalle gebracht und dort aufgestellt.
Laut den Erinnerungen der Bürger von Bitola stand dort auf Deutsch: „3406 deutsche Soldaten ruhen hier“.
