Cargando el mapa…
Durante mucho tiempo se atribuyó el nombre de Velilla a la ciudad cántabra de Vellica, pero esa ciudad se localiza en realidad en Olleros de Pisuerga, lo que descarta cualquier relación entre ambos nombres.
Existe la teoría de que Velilla, formado a partir de Vallella, sea un diminutivo del latín vallis, «valle pequeño», explicación razonable por la situación de la localidad. Según el libro Toponimia palentina, de F. Roberto Gordaliza Aparicio (1993), el nombre equivale a «la pequeña villa del río Carrión». Jesús María Merino Agudo, en Palencia en sus topónimos (2002), interpreta Velilla como «lugar de vigilancia» y el conjunto como «lugar de vigilancia, en la zona del río Carrión».
El complemento «de Guardo» se cambió en 1949 por «del Río Carrión», al estar ya desvinculados los ayuntamientos de ambas localidades.
La existencia de culturas importantes del pasado en Velilla y sus alrededores se apoya en el hallazgo, en 1890, de una lápida funeraria que se conserva en la colección del marqués de Comillas. Su inscripción se interpreta como la de Cado Pedacciano, que erigió el monumento a su amigo Pentovio, de la gente de los Avóleigos, y a su hijo Amio, de treinta años de edad. La primera civilización de la que se tiene constancia en la zona es la del pueblo cántabro.