El territorio que ocupa el municipio de Los Tojos, se encontraba en época romana en la zona de paso de una de las vías secundarias de comunicación que unía el Valle de Campoo con el Valle del Saja, por el Collado de Somahoz y el Puerto de Palombera. Esta vía se ramificaba antes de llegar a Valle, en Cabuérniga, y partía por un lado hacia San Vicente de la Barquera (Portus Vereasueca) y por otro, hacia Suances (Portus Blendium). Es probable que la vía contase con dos ramales, uno que pasaba por el núcleo de Los Tojos y otro por el de Bárcena Mayor. Durante la Alta Edad Media encontramos aquí los tres concejos más meridionales de los diez que formaban el Valle de Cabuérniga, uno de los de la Merindad de las Asturias de Santillana.
En torno al año 1000 aparecen las citas más antiguas sobre las iglesias, ermitas y monasterios de los antiguos concejos; de este modo, la iglesia de Santa María de Barcena Mayor aparece, en el siglo IX, sometida al señorío eclesiástico de Santa María de Yermo, incorporándose en 1168 al monasterio de San Pedro de Cardeña (Burgos) mediante una donación de Alfonso VIII.
Los Tojos formó su propio concejo, siendo sus habitantes gente de behetría que escogía libremente a su señor; aunque a pesar de ello, acabaron como el resto del Valle de Cabuérniga bajo el dominio del señorío de la Casa de la Vega, como así queda recogido en el Apeo de 1404, y en la organización de la administración señorial que ese mismo año hizo el almirante Diego Hurtado de Mendoza, señor de la Vega. En el año 1444, Juan II consolidó la vinculación del valle al señorío de los Vega Mendoza, duques del Infantado. Sin embargo, ya con anterioridad se había iniciado la resistencia contra este señorío, surgiendo el denominado Pleito de los Nueve Valles; éste fue un proceso que enfrentó a nueve valles de las Asturias de Santillana con los duques del Infantado. Se inició en 1544 y fue fallado en 1581 a favor de los Nueve Valles. Fue de vital importancia para el proceso de configuración territorial de Cantabria, ya que causó el retroceso de los dominios señoriales en la región. Además la independencia de esos valles, constituidos en la provincia de los Nueve Valles en 1589, fue el origen de la Provincia de Cantabria de 1778.
Con la resolución definitiva de este pleito, Los Tojos restableció su condición realenga y sus habitantes pasaron a formar parte de la Provincia de los Nueve Valles. En 1517, Laurent Vital, ayuda de cámara de Carlos V, describe le paso del emperador por Los Tojos, después de desembarcar en la aldea de Tazones, cerca de Villaviciosa (Asturias) procedente de Flandes. El emperador se dirigía hacia Castilla, siguiendo la vía de comunicación de origen romano que, desde la Reconquista, se denominó Ruta de los Foramontanos. En 1822, se formó el primer ayuntamiento constitucional del territorio, denominado Correpoco y que comprendía los núcleos de Viaña, Correpoco, Los Tojos y Bárcena Mayor. En 1842, el término municipal adoptó ya, tanto la denominación como los límites actuales, pasando del partido judicial de Puentenansa al de Cabuérniga; en la actualidad forma parte de partido judicial de Torrelavega.