Erste Nennungen derer von Veltheim finden sich unter der Regierung des Königs Heinrich IV. im ausgehenden 11. Jahrhundert. Es ist nicht erwiesen, dass sich die Familie um den heutigen Ort Veltheim an der Ohe ansiedelte und dort eine Wasserburg errichtete. Vielmehr ist dies von dem bereits 966 erwähnten Ort Veltheim am Fallstein bei Osterwieck im Bistum Halberstadt anzunehmen, denn der letzte Graf Siegfried von Osterburg verzichtete 1232 zu Gunsten seines Lehnsherren auf die Kirchen in Veltheim und Osterode am Fallstein und den Zehnt in zwei umliegenden Dörfern.
Der Legende nach findet sich die erste Erwähnung der Familie in der Region nördlich des Harzes mit Ortholph von Veltheim, der 996 dem Turnier zu Braunschweig als Gast beigewohnt hat. Allerdings gibt es dafür keinerlei Belege. Einige der wenigen urkundlich nachweisbaren frühen Vertreter derer von Veltheim werden in einer Urkunde des Halberstädter Bischofs Burchard von Veltheim vom 25. Juli 1087 genannt. Es sind neben dem Bischof sein Bruder Adalgot von Veltheim und dessen Sohn Werner von Veltheim (Velthem).
Bereits am 5. August 1068 hatte König Heinrich IV. an Lantfried, der vermutlich ein Bruder des Bischofs Burchard und des Adelgots von Veltheim war, 44 Hufen Land im Nordthüringau und in der Nordmark, die Burchard zuvor als Lehen besessen hatte, geschenkt. Das deutet darauf hin, dass Burchard der erste seines Adelsgeschlechts war, der vermutlich aus Schwaben nach Sachsen kam und seine Brüder Lantfried und Adalgot nachkommen ließ.
Die von Veltheims waren zu dieser Zeit als Lehnsträger der Bischöfe von Halberstadt nur Edelherren und noch keine Grafen. Der genannte Werner von Veltheim oder sein gleichnamiger Sohn wird erstmals in einer zwischen 1095 und 1101 entstandenen Urkunde des Klosters Lippoldsberg mit dem Adelsprädikat Graf als Werenherus comes bezeichnet, wobei jedoch nicht klar ist, ob mit diesem Werner wirklich ein Vertreter der Familie von Veltheim gemeint ist. Nach Brotruffs rückblickend erzählender „Anhalt. Chronik“ nahm Graf Warner to der Osterburch 1108 die Tochter Elecke des Grafen Otto zur Ehefrau. Urkundlich hingegen wird Werner von Veltheim erst am 3. Oktober 1157 in einer Urkunde Markgraf Albrechts des Bären im Kopialbuch des Klosters Ilsenburg als comes de Osterburch (= Graf von Osterburg) bezeichnet, worauf sich die 2007 erfolgte 850-Jahr-Feier der Stadt Osterburg bezog. Adalgot ist somit nicht nur Stammvater derer von Veltheim, sondern ebenso der Grafen von Osterburg. Die Bezeichnungen Comes de Veltheim und de Osterburg wurden in der Folgezeit oft gleichzeitig verwendet, zuletzt wurde jedoch der Name Veltheim immer mehr zu Gunsten von Osterburg verdrängt. 1238 erfolgt der entscheidende Einschnitt. Der letzte Graf Siegfried von Osterburg und Altenhausen verzichtet auf die meisten seiner Güter und er sowie andere Vertreter der Grafenfamilie finden fortan keinerlei Erwähnung mehr.