La localidad de la Puebla de Castro se formó hacia el siglo XIV como dependiente de la más antigua villa de Castro, creada a partir de la conquista a finales del siglo XI (documentada desde el 1083). Aunque en el municipio hay evidencias de vida humana desde el Neolítico y la Edad del Bronce, como la Cueva de las Campanas, en el congosto de Olvena, al sur del municipio, y también ha pinturas rupestres en el Remosillo que datan de esa última etapa, quizá el elemento patrimonial más insólito que se encuentra es el yacimiento de Labitolosa, en el Tozal del Calvario, donde se pueden apreciar los restos de un antiguo municipium de época imperial romana (floruit entre el siglo I a.C. y el III d.C), que corresponde a un territorio que todavía se explotaba en el siglo VI, de lo que da testimonio la carta de Donación del Diácono Vicente (del año 551). Durante la época islámica también funcionó como terreno estratégico, según testimonian topónimos como la Almenara o Mendaleya (en el Calvario, donde se encuentra Labitolosa). Tras la conquista cristiana se desarrolló la fortificación de Castro, de la que tan solo queda su iglesia románica, San Román, por más que se mantuvo hasta el siglo XVIII. Fue en el XIX cuando se consituyó el municipio de La Puebla de Castro, con Castro como unidad dependiente.