Veldenz qraflığı 1112-ci ildə Kirburq və Şmidburq ailəsinin vildqraflıqlarından qoparılaraq yaradılmışdı. İlk qraf sülaləsinin birbaşa kişi xətti 1260-cı ildə Veldenzli V Gerlax və onun qızı Aqnesin ölümü ilə kəsildi. Onun əri 1260-cı ildə mahalı miras aldı. Qeroldsekli Henrix Veldenz qraflarının və ya Veldenz-Qeroldsek () sülaləsinin ikinci xəttinin qurucusu oldu. 1444-cü ildə qraflıq yeganə varisi Anna ilə evlənmiş Zimmern-Çvaybrükgen hersoqu hakimiyyəti altına düşdü. 1532-ci ildə Çvaybrükgen hersoqluğunun bütün ərazisi hələ uşaq olan Volfqanqa keçdi. 1543-cü ildə Volfqanq yetkinliyə çatdıqda və Marburq müqaviləsini imzaladı və 11 il qəyyum kimi xidmət edən əmisi Veldenz qraflığını verdi.

Rupert 1544-cü ildə vəfat edəndə oğlu Georq İohann onu əvəz etdi. Georq 1563-cü ildə isveçli qızı olan Anna Mariya ilə evləndi. Volfqanq 1553-cü ildə Haydelberq müqaviləsi ilə Veldenz-Pfaltsdan Elzasdakı Lützelşteyn qraflığına qədər uzanan bütün Vittelsbax qollarının qarşılıqlı mirasını tənzimləmişdi. Georg Hansın nəvəsi Leopold Lüdviq fon Lützelşteyn qanuni övladları olmadan 1694-cü ildə öldü və Veldenz qraflığı Çvaybrükgen xəttinə, spesifik olaraq İsveç Kralı qayıtdı.

1801-ci ildə Birinci Fransa İmperiyasının Saar departamentinə daxil edildi. 1815-ci il Vyana Konqresi, Mozel üzərində yerləşən qraflığın kiçik hissəsini Prussiyaya, qalan hissəsini isə Bavariyaya verdi.

1. Emix, Kirburq və Şmidburq qrafı (1086–1113)
2. I Gerlax (1113–1146)
3. II Gerlax (1146–1186)
4. III Gerlax (1186–1214)
5. IV Gerlax (1214–1254)
6. V Gerlax (1254–1260)
7. Aqnes (1260–1277)
8. I Henrix (1277–1298) ∞ Aqneslə evləndi
9. Valter (1298–1327)
10. Georq (1327–1347)
11. II Henrix (1347–1378)
12. II Fridrix (1378–1396)
13. III Henrix (1378–1389)
14. IV Henrix (1389–1393)
15. (1393–1444)
16. (1444)
17. (1444–1489)
18. (1489–1514)
19. (1514–1532)
20. Volfqanq (1532–1543)
21. (1543–1544)
22. Georq İohann (1544–1592)
23. Georq Qustavus (1592–1634)
24. Leopold Lüdviq (1634–1694)