En 1257, Sancho Fernández de Azagra permutó el castillo de Arcos y otra fortaleza con el rey Jaime I, a cambio de Villafeliche. En 1258, Jaime I lo legó a Teresa Gil de Vidaure y al infante Pedro. En 1357, Pedro IV ordena fortificar el lugar de Arcos, ante el temor a que éste sea ocupado por los castellanos; en febrero de 1358 su defensa se refuerza con ballesteros. Dada la proximidad con la frontera castellana, el recinto amurallado que protege la villa pudo erigirse también en el siglo XIII.
La aldea de Arcos, asentada en la cumbre de un amplia loma, estaba protegida por un recinto fortificado, del que se conocen diversas estructuras:
- Castillo: Es muy posible que se situase en la Peña de Arcos, saliente del espolón sobre el que se asienta la villa, con buenas condiciones estratégicas. Otro emplazamiento probable es la amplia parcela en la que se asienta la monumental iglesia barroca, edificio que, por sus dimensiones, debió integrar espacios ajenos a al templo medieval.
- Portal de la Catarra: Arco apuntado de grandes dimensiones. Extramuros tiene adosado un edificio, levantándose sobre el paso mediante un forjado de madera.
- Portal de Teruel: Portal muy transformado, que en la actualidad tiene la apariencia de una torre-puerta cubierta mediante forjado de madera. Comunica el interior del recinto con el Arrabal y el Camino de Teruel, pudiendo considerarse como el principal acceso de la villa.
- Posible portal “de la Pecha”: Aunque no se conservan evidencias visibles, debió existir un portal o postigo en el callejón que une las calles de la Pecha y Manuel Murría.
- Trazado y lienzos de la muralla: Actualmente no hay lienzos visibles de la muralla, ocultos por los edificios adosados extramuros.