Der Gräbernachweis in der Abteilung Kriegsgräberdienst umfasst nach § 2 Abs. 1 Ziffer 3 der Satzung des Volksbundes die Feststellung und den Nachweis der Kriegsgräber, wie auch alle Fragen der Identifizierung der darin bestatteten Toten. In allen Fragen der Suche nach Gräbern, der Identifizierung von Unbekannten, der Ermittlung von Hinterbliebenen, der Entschlüsselung von Erkennungsmarken und anderem arbeitet der Gräbernachweis eng mit dem Bundesarchiv, Abteilung PA, der ehemaligen Deutschen Dienststelle (WASt) in Berlin zusammen.

Die Zentralgräberkartei des Volksbundes, deren Anfänge auf das Jahr 1945 zurückgehen, umfasst eine alphabetische Namenkartei mit rund 2,5 Millionen Meldungen zu gefallenen deutschen Soldaten und eine nach Ländern und Grablageorten gegliederte Friedhofskartei, in der deutsche Gefallene mit nachweisbarer Grablage enthalten sind. Hierin nicht enthalten waren Grab- und Todesmeldungen für das Gebiet der ehemaligen Sowjetunion, die sich im Bundesarchiv in Berlin befinden. 1994 begann die Übermittlung dieser Meldungen an den Volksbund. Dazu war es notwendig, ein EDV-gestütztes Informationssystem zur Speicherung der Daten von Kriegstoten und Vermissten sowie Angehörigen zu entwickeln.

Mit dem Einsatz des neuen EDV-Programms wurde ein wichtiger Schritt zur Optimierung der Arbeitsabläufe vollzogen. Die gespeicherten Grabinformationen dienen heute der Vorbereitung der Umbettungen ebenso wie der Auswertung der Arbeitsergebnisse des Umbettungsdienstes und der Aufbereitung der Unterlagen für die namentliche Kennzeichnung der Gräber. Die elektronische Datenspeicherung und die 2004 begonnene optische Archivierung des Schriftwechsels mit den Angehörigen erleichtert zudem die Auskunftserteilung. Die Vorgangsregistratur umfasst über 800.000 inzwischen digitalisierte Einzelvorgänge mit Ermittlungen, Daten und Auskünften zu den Schicksalen und Grablagen ebenso vieler Vermisster und Gefallener.

Seit der Wiederaufnahme der Umbettungen im Jahre 1992 konnten die Gebeine von über 1.000.000 deutschen Kriegstoten in Osteuropa geborgen werden. Für diese Aufgabe stellt der Gräbernachweis genaue Angaben der Grablagen bereit, die es noch heute dazu beitragen, die oberirdisch nicht mehr erkennbaren Ursprungsgrablagen aufzufinden. Die vom Umbettungsdienst notierten Feststellungen am Grab (Umbettungsprotokolle) werden im Gräbernachweis mit aller Sorgfalt ausgewertet. In Zusammenarbeit mit dem Bundesarchiv können so viele bislang als unbekannt bestattete Gefallene identifiziert und damit wieder namentlich bekannt gemacht werden. Neben den umgebetteten Kriegstoten werden auch diejenigen, die nicht mehr geborgen werden konnten oder „unter den Unbekannten“ ruhen, namentlich ermittelt und erfasst.

Um die Namen der Kriegstoten auf Grabzeichen oder Gedenktafeln verzeichnen zu können, mussten früher tausende von Beschriftungszetteln erstellt werden. Heute geht dieser Arbeitsvorgang aufgrund der Datenspeicherung wesentlich rationeller vonstatten.

Steinmetze erhalten Computerdateien mit den Namen und persönlichen Daten der Gefallenen sowie der Bezeichnung der Grablage. Computergesteuerte Automaten zur Gravur schreiben die Namen auf die Natursteintafeln.

1999 begann der Gräbernachweis damit, die Informationen über Kriegstote und Vermisste im Internet zu veröffentlichen, sodass Angehörige und Interessenten eigenständig recherchieren können. Heute stehen weit über vier Millionen Datensätze in der „Gräbersuche online“ auf der Internetseite des Volksbundes zur Verfügung.