Los actuales Caminos Lebaniegos recuperan —salvo algunas modificaciones de orden práctico— antiquísimas vías de comunicación entre la Meseta, la comarca de Liébana y la costa cantábrica, que fueron utilizadas en ambos sentidos ya desde la antigüedad por legiones romanas, viajeros, comerciantes, pastores y también —a partir del siglo VIII— por peregrinos que se dirigían al monasterio de Santo Toribio al objeto de venerar el Lignum Crucis, la mayor reliquia que se conserva de la Cruz de Jesucristo.
Existe cierta confusión entre dos prelados del cristianismo primitivo, ambos con el nombre de Toribio, que aparecen en la historia del citado monasterio, si bien uno de ellos correspondería al momento fundacional, hacia el siglo VI, y otro contribuyó decisivamente a su auge como lugar de peregrinación a partir del siglo VIII; también hay quien piensa que se trataría de un mismo personaje, pero cuya historia nos habría llegado a través de dos narraciones diferentes; de hecho no es fácil discernir ni siquiera a cuál de los dos se atribuye santidad:
Según cuenta la leyenda, Toribio de Palencia era un monje anacoreta que habitaba una ermita en las afueras de la ciudad, y que mientras predicaba fue apedreado por los lugareños, partidarios del paganismo. Expulsado de Palencia, el monje y sus acólitos decidieron trasladarse a un paraje remoto, perdido en un rincón de las montañas cántabras, donde fundarían el monasterio de San Martín de Turieno (en honor a San Martín de Tours, advocación por excelencia de la época); al principio se instalaron en pequeñas ermitas diseminadas, alguna de las cuales todavía resta en pie, donde practicaban una vida ascética, en conexión con la naturaleza y con Dios; el núcleo se consolidó y a finales del siglo VI se erigió una iglesia primitiva, que en el siglo XI sería substituida por un templo románico y después, en el XIII, por el actual, ya bajo su nueva denominación como Santo Toribio de Liébana.
El segundo personaje —éste bien documentado— es el obispo Toribio de Astorga, que vivió entre los años 402 y 476 (anterior por tanto a la fundación del monasterio, pero cuyos restos mortales serían trasladado allí siglos más tarde). Era hijo de una familia noble de la Gallaecia romana, provincia que hacia el 409 quedó bajo dominio suevo; en su juventud viajó a Roma y a Jerusalén, donde el patriarca Juvenal le obsequió con varias reliquias que provenían del Santo Sepulcro, entre ellas el Lignum Crucis, fragmento del brazo izquierdo de la Cruz de Cristo, y que llevó consigo de vuelta a Hispania. Tras pasar por la parroquia de Tuy, en Galicia, y fruto de sus buenas relaciones con el papa León I, fue nombrado en el año 444 obispo de Astorga, sede desde la cual luchó contra el priscilianismo, corriente muy extendida y que consideraba una herejía. En el siglo VIII, casi 250 años después de su muerte, sus restos —junto con el Lignum Crucis— fueron trasladados al recóndito monasterio de San Martín de Turieno, a fin de protegerlos del avance musulmán; la devoción por la reliquia fue en aumento y el lugar se convertiría muy pronto en uno de los focos más importantes de peregrinación cristiana; más tarde, en el siglo XI, dicho cenobio pasó a denominarse Santo Toribio de Liébana, como homenaje al obispo allí enterrado.
El esplendor del monasterio también está vinculado a otra figura de gran relevancia en su época: el monje Beato de Liébana (730-798), erudito de origen mozárabe que, tras huir del territorio andalusí, se refugió entre estos muros a mediados del siglo VIII; fue aquí donde escribiría entre los años 776 y 786 la compilación en doce libros de Comentarios al Apocalipsis de San Juan, y también donde conoció a Eterio, obispo titular de Osma, con quien redactó el Apologeticum Adversus Elipandum contra los obispos Elipando de Toledo y Félix de Urgell, a quienes acusaba de adopcionismo; mantuvo una fluida amistad con Alcuino de York, abad de Tours y consejero del rey franco —y futuro emperador— Carlomagno, actuando como mediador entre éste y los reyes asturianos. Además de ejercer gran influencia sobre Alfonso II el Casto, monarca clave en la consolidación del reino, Beato también está intrínsecamente ligado a la inventio jacobea, pues fue uno de los primeros en afirmar que el apóstol Santiago había evangelizado España (manifestación con evidente voluntad política, al objeto de fortalecer la identidad e ideología del reino astur, no sólo en su resistencia ante el emirato cordobés, sino también ante la actitud colaboracionista de la jerarquía eclesiástica toledana).
La abadía, a pesar de estar situada en un valle remoto y aislado, lejos de los centros de poder, se convirtió en un gran foco cultural y religioso, con biblioteca y scriptorium donde los monjes copiaban e iluminaban códices. La peregrinación para venerar la reliquia del Lignum Crucis llegó a atraer tantos fieles que, en el año 1512, el papa Julio II otorgó al monasterio el privilegio de celebrar jubileos in perpetuum, durante los cuales se concede indulgencia plenaria a quienes allí acuden (privilegio o gracia que durante siglos sólo compartió con otros tres lugares santos: Roma, Jerusalén y Santiago de Compostela).
Así, de la misma manera que los que peregrinaban a Roma recibían el sobrenombre de romeros, a Jerusalén palmeros y a Santiago concheros (por el símbolo de la vieira, la concha marina), los peregrinos que iban a Santo Toribio eran conocidos como crucenos, en referencia a la reliquia de la Cruz. Es también por ello que, en la señalización de los diferentes caminos lebaniegos, se utiliza el símbolo de una cruz de color rojo.
Hasta hace unas décadas, el jubileo de Santo Toribio se limitaba a la semana inmediata a la festividad del patrón; pero en 1967 dicho criterio fue modificado, pasando a celebrarse aquellos años en que el día del santo —el 16 de abril— cae en domingo, y desde entonces su duración es de un año completo a partir de dicha fecha. Al igual que sucede en Compostela, durante los Años Jubilares Lebaniegos aumenta notablemente el número de peregrinos —mejor dicho, crucenos— a Santo Toribio.