Die Waldsteiner stammen ebenso wie die Herren von Lämberg, Michaelsberg, Welesin, Dietenicz, Zwirzeticzky und Wartenberg aus dem Haus der Markwartinger. Mitglieder dieses weitverzweigten Geschlechts, seit 1059 belegt, im Norden und Nordosten Böhmens ansässig, waren einflussreiche Persönlichkeiten am Hof der Dynastie der Přemysliden in Prag.
Der erste bekannte Träger des Herkunftsprädikates „von Waldstein“, Zdeněk von Waldstein (1242–1278), war Sohn des königlichen Burggrafen auf Jungbunzlau, Jaroslav von Hruštice (1198), von welchem die Burg Waldstein als Herrensitz auf drei Felsen im Waldgebiet südlich von Turnau erbaut wurde und heute noch als Ruine erhalten ist. Von dieser Burg stammt der Prädikatsname. Zdeněk soll zusammen mit seinen vierundzwanzig Söhnen (nach anderen Angaben waren es sechs Söhne) an der Seite des Königs Přemysl Ottokar II. in den Krieg gegen die Pruzzen gezogen sein.
Nach seinem Tod wurde der Besitz aufgeteilt und das Geschlecht verzweigte sich in mehrere Linien, die sich nach dem jeweiligen Herrschaftssitz benannten. Die Hauptsitze der Waldsteiner waren in Lomnitz, Stephanitz, Pirnitz, Groß Skal, Aujest, Hostinitz, Bílé Poličany, Miletin, Münchengrätz, Dobrowitz, Arnau, Böhmisch Hermannitz, Jettenitz und Dux. Der reichste Zweig waren vermutlich die mährischen „Waldstein aus Pirnitz“ („Valdštejn z Brtnice“).
Seit dem 15. Jahrhundert findet sich der Name Waldstein im öffentlichen Leben wieder. Mitglieder der Familie wurden hohe Geistliche und Gelehrte, Militärs, Landeshauptleute der böhmischen Landkreise, stellten Beisitzer am Land- und Kammergericht und übernahmen hohe Hofämter wie das des Kämmerers, Oberstrichters, Oberstmünzmeisters und Obersten Vorschneiders bis hin zum Amt des Oberstburggrafen und Statthalters des Böhmischen Königreiches. Der bekannteste Vertreter der Familie, Wallenstein, kam aus einem Seitenzweig mit weniger als 100 erbuntertänigen und abgabepflichtigen Bauern in der kleinen Grundherrschaft Hermanitz an der Elbe.
Vermögen und Grundbesitz, welche die Familie seit dem Mittelalter in Böhmen und Mähren erworben hatten, wurden nach der Schlacht am Weißen Berg zumindest demjenigen Teil der Waldsteiner, die sich zum böhmischen Adel bekannten und dem protestantischen Glauben nahestanden, konfisziert und meist von Wallenstein aufgekauft. In der Mitte des 18. Jahrhunderts waren die Seitenzweige bis auf die Linien in Münchengrätz und Dux ausgestorben oder, soweit protestantisch, emigriert. Den Namen Waldstein-Wartenberg nahm die Familie im Jahr 1758 nach dem Aussterben der Herren von Wartenberg an, mit denen sie gemeinsame Vorfahren hatten.