Das GHdA von 2004 bestätigt, dass es mehrere, unabhängig voneinander bestehende Adelsgeschlechter von Veltheim gegeben hat, deren Verwandtschaft untereinander urkundlich nicht nachweisbar ist. Neben den Edelherren und Grafen von Veltheim beziehungsweise Osterburg gab es seit der Mitte des 12. Jahrhunderts noch das Ministerialengeschlecht von Veltheim im Raum Braunschweig, wo die Burg Veltheim liegt. Die Möglichkeit, dass diese Ministeriale, die später in den Ritterstand erhoben worden sind, von den eingangs genannten Grafen abstammen, ist nur eine sehr geringe und beruht lediglich auf folgender Erwägung:
Graf Werner III. von Veltheim hatte aus seiner Ehe mit Adelheid von Ballenstedt zwei Söhne. Der älteste Sohn Werner fiel vor Brandenburg und Graf Albrecht setzte das Geschlecht fort. Möglicherweise gingen aus dieser Ehe noch weitere Kinder hervor. Dazu könnte der 1141 genannte Ministeriale Othelricus de Velthem (1160 und in der Folgezeit als Rotherus de Feltem oder ähnlich erwähnt) gehört haben, auf den sich das Ministerialiengeschlecht derer von Veltheim zurückführen lässt. Diese Variante ist umstritten, da es nur selten vorkommt, dass Edelherren zu Ministerialen degradiert werden oder sich in dieser Zeit freiwillig degradieren lassen.
Die Ministerialen von Veltheim führten seit 1391 das Balkenwappen anstatt des bis dahin verwendeten Lindenzweiges. Das Balkenwappen war jedoch das Wappen der Grafen von Veltheim beziehungsweise Osterburg. Ob diese Änderung als Ausdruck erfolgt ist, dass die Ministerialen von den Osterburgern abstammten oder weil sie nur Burgmannen der Osterburger waren, bleibt umstritten. George Adalbert von Mülverstedt kommt in seiner Schrift Die Grafen von Osterburg und Lüchow zu letzterem Ergebnis. Die vorhandenen Quellen zu den Veltheims im 13. und 14. Jahrhundert sind noch nicht entsprechend intensiv aufgearbeitet worden und lassen Fragen zu den Nachfahren derer von Veltheim offen.
Sicher ist, dass die von Veltheim sich in dieser Zeit ebenfalls auf der Wasserburg Bartensleben in Bartensleben niederließen. Erstmals urkundlich bestätigt ist dies, als Ludolf I. von Veltheim am 18. Oktober 1400 durch einen Lehnsbrief des Erzbischofs von Magdeburg in Besitz der Burgstelle kam. Geschichtlich überliefert ist darüber hinaus, dass einer seiner Nachfolger, Hilmar I. von Veltheim, 1467 mit dem Dorf Bartensleben belehnt wurde.
Zwischenzeitlich wurde die Burg Veltheim, der Stammsitz derer von Veltheim, von Bürgern aus Braunschweig erheblich zerstört, die gegen die Behinderung ihrer Handelswege nach Osten kämpften. Daraufhin verkaufte um 1494 Cord von Veltheim die zerstörte Burg an die Familie von Honrodt. Damit endete die Geschichte derer von Veltheim in Veltheim an der Ohe vorläufig. Die Geschichte derer von Veltheim führt sich ab da hauptsächlich in der Region Bartensleben und umliegenden Gemeinden fort. In der Bartenslebener Kirche finden sich insgesamt 35 Epitaphen derer von Veltheim. Des Weiteren besitzt die Kirche eine einzeln zugängliche Empore, die zu ihrer Zeit nur der Familie von Veltheim zugänglich war.
Zwischen 1303 und 1318 ging die Burg Harbke südlich von Helmstedt an die von Veltheim über, die sie bis zum Einmarsch der Russen 1945 besaßen. Zwischen 1573 und 1579 wurde der derzeitige Schlossbau im Renaissance-Stil errichtet. Mitte des 18. Jahrhunderts erfolgte ein barocker Umbau der Wirtschaftsgebäude, außerdem wurde ein französischer Park angelegt, der sich durch zahlreiche seltene Bäume auszeichnete, und im 19. Jahrhundert im englischen Stil verändert und ausgebaut wurde. Deshalb suchte Goethe im Jahr 1805 von Helmstedt aus Schloss Harbke auf, um hier den Berghauptmann v. Veltheim kennenzulernen und botanische Studien zu treiben. Zu Harbke gehörte bis 1854 auch das Gut Aderstedt und das Gut Groppendorf. Leider unterließen es die neuen Machthaber, das schadhaft gewordene Dach zu erneuern, sodass das 1945 noch völlig unversehrte Schloss Harbke in den folgenden Jahrzehnten zerfiel. Gegenwärtig kann nur noch eine eindrucksvolle Ruine sowie der rekonstruierte schöne Landschaftspark bestaunt werden.
Seit 1356 ist die Wasserburg Destedt im Besitz der Veltheims. 1430 und 1432 wurde sie von den Braunschweigern eingenommen, zerstört und nach dem Abbruch in Brand gesetzt. Nach Merian soll sie generationenlang in Trümmern gelegen haben. Etwa zweieinhalb Jahrhunderte später, nach den Wirren des Dreißigjährigen Krieges, nahm der damalige Besitzer, Joachim Ludolf von Veltheim, einen Neubau der Oberburg in Angriff. Dadurch entstand im Jahre 1693 der heutige Schloss im Barockstil. Bei der Gestaltung hat vermutlich der braunschweigische Landesbaumeister Johann Balthasar Lauterbach eine wesentliche Rolle gespielt. Schloss und Gut befinden sich bis heute im Besitz der Familie, zugleich mit dem benachbarten Rittergut Cremlingen. Georg Philipp von Veltheim, ab 1740 braunschweigischer Hofjägermeister, hat wahrscheinlich 1750 den Grund zur Anlage des Parks gelegt, indem er den Pfarrhof durch Landtausch erwarb. Zwischen 1750 und 1770 wurden die ersten Bäume gepflanzt. Johann Friedrich von Veltheim (1731–1800) beabsichtigte nach seiner Heirat mit Sidonie von Münchhausen, Tochter des seinerzeit bekannten Botanikers Otto von Münchhausen auf Schwöbber, den kleinen Französischen Garten westlich des Schlosses zu einem weitläufigen Landschaftspark zu erweitern. Ab 1768 begann die Anlage eines – weniger nach englischen als nach deutschen Vorstellungen geprägten – Parks unter Mitarbeit des Gärtners aus Schwöbber. Noch heute weist die Anlage einige Besonderheiten auf, hierunter die überwiegend amerikanischen Bäume, die General Friedrich Adolf Riedesel, Freiherr zu Eisenbach, von Amerika herübergesandt haben soll.
1420 erwarben die Veltheim das Rittergut Glentorf bei Königslutter. Seither ist ein Familienzweig bis heute dort ansässig.
Im Jahr 1439 erwarben die Veltheims die Markgrafenburg auf der Burg Alvensleben bei Haldensleben als Lehen von den Magdeburger Erzbischöfen, nachdem die Familie von Alvensleben bereits um 1270 ihren Hauptsitz auf die Burg Erxleben verlegt hatte. Sie war als sogenannte Hinterburg Teil der Befestigungsanlage und wurde seit der Erweiterung durch ein Herrenhaus im 18. Jahrhundert als “Veltheimsburg” bezeichnet – vermutlich zur besseren Unterscheidung von der Hauptburg Alvensleben, die weiter zum erzbischöflichen, später brandenburgischen Amt Alvensleben gehörte. Im Zuge der Separation konnte der Landrat August Wilhelm von Veltheim (1798–1848) 1837 das Gelände der inzwischen weitgehend abgetragenen Hauptburg hinzu erwerben und in einen Landschaftspark umgestalten. Die Gebäude der Veltheimsburg wurden 1882 und 1910 in romantisierender Form ausgebaut. Das Gut Veltheimsburg und die Burg blieben bis zur Enteignung durch die Bodenreform 1945 im Veltheimschen Besitz.
Von 1452 bis 1457 waren die Veltheims Herren auf Burg Scheidungen. Bertram, Ludwig und Hans, Gebrüder, Söhne von Hans III. von Veltheim erwarben 1452 Burgscheidungen. Bertram von Veltheim verkaufte es jedoch bereits 1457 weiter.
Um 1586 wird Achatius von Veltheim in Ostrau genannt, der mit dem Schloss Ostrau am 1. Februar 1586 von Kurfürst August von Sachsen belehnt wurde. Die Veltheims ließen die Burg zu einem vierflügeligen Renaissanceschloss mit weiträumigen Wirtschaftshof umbauen. Im Dreißigjährigen Krieg konnte sich die Burg gegen ein schwedisches Korps unter General von Königsmarck und gegen kaiserliche Truppen unter General Gallas halten. Otto Ludwig von Veltheim ließ ab 1713 die alten Gebäude abreißen und durch den französischen Architekten Louis Remy de la Fosse ein Schloss im Stile des französischen Barock erbauen. Es zählt zu den wertvollsten Barockbauten des Landes heutigen Landes Sachsen-Anhalt.
1832 erwirbt Wilhelm von Veltheim das Stammgut Veltheim an der Ohe für die Familie zurück. Bis heute genießt die Familie die besondere Hochachtung der Einwohner, zumal sich die Schlossherren stets sehr volksnah zeigten. So verfügt die Gutsherrschaft schon seit mehr als 400 Jahren über das Kirch-Patronat. Der Landwirt Alexander von Veltheim ist derzeit Bürgermeister von Veltheim an der Ohe.
Das Genealogische Handbuch des Adels spricht im 18. und 19. Jahrhundert von zwei Linien der Familie von Veltheim, einer sogenannten Schwarzen Linie und einer Weißen Linie. Bereits 1406 teilten sich die Brüder Hans und Heinrich (IV.) von Veltheim „sämtliche Güter an Lehen und Erbe“ und begründeten die sog. „Weiße Linie“ (Hans) sowie die „Schwarze Linie“ (Heinrich IV.).
August Ferdinand von Veltheim, Vertreter der Schwarzen Linie und Gutsherr auf Harbke, königlich preußischer Berghauptmann, wurde am 6. Juli 1798 in Berlin in den preußischen Grafenstand erhoben. Am 15. Oktober 1840 erfolgte die preußische Verleihung der Erbmarschallwürde des Herzogtums Magdeburg in Berlin für Röttger Graf von Veltheim, Majoratsherr auf Harbke, Aderstedt und Groppendorf, Erbküchenmeister des Herzogtums Braunschweig.
Wappen der Grafen von Veltheim
Ludolf Heinrich von Veltheim heiratete 1888 Viktoria Wanda, Gräfin von Wylich und Lottum (* 1861 † 1933), Erbin des Fideikommisses Lissa bei Breslau; er nannte sich daraufhin von Veltheim-Lottum. Ihr Sohn Malte von Veltheim-Lottum trat 1934 das Erbe seines mütterlichen Grossvaters Wilhelm Malte II., Reichsgraf von Wylich und Lottum, seit 1861 Fürst und Herr zu Putbus, an und nannte sich nun Malte von Putbus (* 1889 † 1945). Er starb im Konzentrationslager Sachsenhausen. Seinem Sohn Franz von Putbus (* 1927 † 2004) wurden durch die Bodenreform 1945 die Besitzungen des Hauses Putbus – einer Nebenlinie des einstigen Fürstenhauses von Rügen – enteignet, die rund ein Sechstel der Insel Rügen umfassten. Er erhob nach 1990 vor Gericht erfolglos Ansprüche auf die Rückerstattung der umfangreichen Liegenschaften. Seit 1951 führte er den Titel Fürst von Putbus. Er kaufte jedoch ein Palais am Circus in Putbus und geringe Teile der Ländereien zurück, die sein Sohn Malte übernahm.
In Anerkennung seiner Dienste für das Herzogtum Braunschweig/Lüneburg wurde Hans von Veltheim (Weiße Linie), k. u. k. Leutnant, am 11. Juli 1848 in den Freiherrenstand erhoben. Am 8. November 1851 erfolgte für denselben die österreichische Prävalierung des Freiherrntitels.
Nach dem Zweiten Weltkrieg wurde die Familie umfangreich enteignet. Sie flüchtete in die westlichen Besatzungszonen und verlor durch Bodenreform Besitzungen wie Bartensleben, Veltheimsburg (Bebertal), Putbus, und Ostrau, dessen letzter Besitzer der Indologe, Anthropologe und Weltreisende Hans Hasso von Veltheim war. Mit seinem Tod ohne männliche Nachkommen starb 1956 die Linie Ostrau derer von Veltheim aus.
Nach der deutschen Wiedervereinigung 1990 kauften Jobst von Veltheim und sein ältester Sohn Nikolaus den ererbten Bartenslebener Forst im Jahre 1996 zurück. Heute befindet sich Schloss Bartensleben in Privatbesitz und verfällt zusehends.