Esisten diverses hipótesis avera del orixe del nome de Cuéllar y el so significáu. El primer autor qu'escribió sobre ello foi l'historiador Diego de Colmenares, qu'atribuyó a Cuéllar ser la famosa ciudá romana de Colenda pola semeyanza de vocablos, teoría que tamién sostuvo Federico Wattenberg na so obra, al igual que lu fixeron Madoz, Piferrer, y Somorrostro. Nun paez tener muncha veracidá esta atribución, pos ta basada na semeyanza del nome, ensin investigar otros aspeutos. Per otru llau, tampoco s'alcontraron hasta'l momentu restos romanos na villa, lo que fai más improbable que'l nome de Cuéllar derive del de Colenda y collo pueda atribuyise la identidá d'esa ciudá a esti conceyu.