Según puede deducirse de los escasos restos arquitectónicos, de las noticias de las fuentes escritas tanto musulmanas como cristianas y del análisis del plano urbano actual de Bolea, en época andalusí este enclave contaría con los elementos propios de los asentamientos castrales de mayor importancia: un recinto amurallado, un reducto defensivo posiblemente situado en su cota más alta, un hábitat y arrabales extramuros. Sin embargo, pese a los poco fundamentados intentos de identificación del castillo o de parte de las murallas en el entorno de la colegiata llevados a cabo en las últimas décadas, hasta hace pocos años no se conocía ningún vestigio construido que pudiera asociarse con seguridad con las estructuras defensivas de la Bolea islámica.
Sin embargo, en 2017, en el curso de las obras de rehabilitación de un edificio situado en la plaza Mayor apareció un interesante lienzo de muro de características inequívocamente andalusíes, que ha sido puesto en relación con la antigua muralla de la población por el arqueólogo José Ángel Asensio.
El muro localizado tiene una longitud de 15-16 m y una altura total de unos 2,60 m. Se conservan a la vista nueve hiladas de sillares dispuestos a tizón, muy regulares, de sección cuadrada, trabados con finos tendeles de mortero de yeso, que configuran un aparejo muy similar a los de otras obras defensivas andalusíes de esta región. Por otro lado, en las hiladas inferiores del muro se pueden ver dos retranqueos sucesivos que conforman una zarpa escalonada también presente en otras fortificaciones del entorno, como en la muralla de Huesca, Cuarte, la Iglesieta de Gabarda o la torre de la Magdalena de Panzano. El mencionado arqueólogo concluye que este aparejo es, formalmente, característico de la arquitectura monumental andalusí de la Marca Superior, empleado sobre todo en fortificaciones urbanas y rurales.
Este muro se prolonga a la finca colindante por el lado oeste, enlazando con una estructura de trazado ligeramente curvo, que ha resultado ser, tras su estudio, un cubo de la muralla andalusí, que enlaza con otro tramo de muro que continuaría el recinto fortificado. Estos tramos están realizados con sillares a tizón de menores dimensiones que los existentes en el bar La Muralla, pero también presentes en ejemplos próximos como la muralla de Huesca.
Asensio concluye retomando una hipótesis ya enunciada por Antonio Naval Mas en 1983, según la cual en esta zona pudo encontrarse uno de los accesos del recinto amurallado de Bolea. Según el arqueólogo, este acceso pudo tener estructura en codo y estar protegido en sus flancos por el torreón circular localizado y un quiebro en el trazado de los lienzos de muralla contiguos.