Die Ursprünge der Udonen (auch Grafen von Stade genannt) als sächsisches Hochadelsgeschlecht reichen bis in das 9. Jahrhundert zurück. Der früheste namentlich bekannte Ahnherr der Familie ist Graf Abbo, der um das Jahr 810 geboren wurde, wenngleich über seine genaue Herkunft wenig bekannt ist. Deutlicher greifbar wird die Familie durch kriegerische Ereignisse an den sächsischen Grenzen: Ein Nachfahre Abbos, Graf Lothar I., fiel im Jahr 880 in der Schlacht bei Ebstorf gegen ein Wikingerheer. In der Schlacht bei Lenzen im Jahr 929 fielen zudem zwei weitere Vorfahren (beide mit dem Namen Lothar bzw. Liutheri) im Kampf gegen slawische Stämme.
Der namensgebende Leitname „Udo“ (später oft zu „Lothar-Udo“ oder „Luder-Udo“ kombiniert) fand erst im 10. Jahrhundert Eingang in das Geschlecht. Graf Heinrich I. „der Kahle“ († 976) heiratete Judith (oder Jutta), die Tochter des Grafen Udo I. aus der Wetterau und dem Rheingau, wodurch dieser Leitname in die Familie der Stader Grafen übernommen wurde.
Ein zentrales Merkmal der udonischen Herkunft war ihre enge Verwandtschaft zum ottonischen Königshaus. Der Chronist Thietmar von Merseburg betont, dass sein Großvater Heinrich I. der Kahle nah mit Kaiser Otto I. verwandt war. Diese Nähe zeigt sich auch darin, dass Heinrichs Tochter Hathui ein Patenkind Ottos des Großen war. Es wird in der Forschung vermutet, dass bereits die Ehefrau eines früheren Lothar, Schwanhild (Suuanihilt), königlicher Abstammung war, möglicherweise eine Tochter König Heinrichs I..
Die Familie baute ihre Macht auch durch vielfältige dynastische Heiratsverbindungen aus:
- Grafen von Walbeck und Thietmar von Merseburg: Kunigunde, eine Tochter Heinrichs des Kahlen, wurde mit dem Grafen Siegfried I. von Walbeck vermählt. Aus dieser Ehe ging unter anderem der berühmte Chronist und Bischof Thietmar von Merseburg hervor. Thietmars Chronik ist heute die wichtigste und verlässlichste Quelle für die frühe Familiengeschichte der Udonen. - Grafen von Katlenburg: Die Grafen Udo und Heinrich von Katlenburg gehörten als Seitenlinie ebenfalls zu den Udonen. Sie waren sehr wahrscheinlich Söhne des udonischen Grafen Luder-Udo I., der 994 im Kampf gegen die Normannen fiel. - Verbindung zu den Sponheimern: Im 12. Jahrhundert heiratete Markgraf Rudolf I. von Stade die aus dem rheinisch-mitteldeutschen Raum stammende Richgard (Richardis) von Sponheim, Tochter des Magdeburger Burggrafen Hermann. Diese Ehe brachte umfangreiche Ländereien und weitreichende Netzwerke in die Familie ein.
Die Ehe von Rudolf I. und Richgard brachte die letzte Generation der Udonen hervor, zu der neben der späteren Äbtissin Richardis von Stade und der dänischen Königin Liutgard von Salzwedel auch die Brüder Udo IV., Rudolf II. und Hartwig I. gehörten. Mit dem gewaltsamen Tod von Udo IV. (1130) und Rudolf II. (1144) erlosch der weltliche Mannesstamm der Dynastie, da der letzte verbleibende Bruder, Hartwig I., als Erzbischof von Bremen dem geistlichen Stand angehörte und keine legitimen Erben hinterlassen konnte. Dies führte nach Hartwigs Tod zum endgültigen Ende des Hauses und zu erbitterten Streitigkeiten um das Erbe der Udonen (die Grafschaft Stade) zwischen dem Erzbistum Bremen und Herzog Heinrich dem Löwen.