ต้นกำเนิดของชื่อเมืองที่เป็นไปได้ประการหนึ่งคือคำในภาษาละตินว่า วัลลิส (VALLIS) หมายถึง "หุบเขา" กับคำในภาษาเคลติกว่า โตลีตุม (TOLITUM) หมายถึง "ที่บรรจบของสายน้ำ" หรือ "เมืองในเมฆ" นอกจากนี้ ชื่อเมืองนี้ยังเชื่อมโยงกับชื่อภาษาอาหรับของเมือง بلد الوليد (ออกเสียงว่า บะละดัลวะลีด) หมายถึง "เมืองของวะลีด" โดยอัลวะลีดที่ 1 (Al-Walid I, 668 - 715) เป็นชื่อกาหลิบแห่งราชวงศ์อุไมยัดซึ่งเป็นผู้ปกครองอัลอันดะลุส (สเปนสมัยมุสลิมมีอำนาจ) ระหว่างปี ค.ศ. 705 - 715

อีกประการหนึ่ง เมืองนี้มีชื่อเล่นที่นิยมเรียกว่า ปูเซลา (Pucela) รากศัพท์ของชื่อนี้ยังไม่เป็นที่ชัดเจน แต่อาจจะมาจากคำที่ใช้เรียกอัศวินกลุ่มเล็ก ๆ กลุ่มหนึ่งที่ติดตาม "คัวนา เด อาร์โก"