La capital y principal ciudad de la provincia o distrito de Barbithaniyya musulmana era la de Barbastro, que en el año 802 se reducía únicamente a un castillo en un peñasco fundado por Jalaf ibn Rhasgıd ibn Asad en la primera mitad del siglo IX. Al-‘Udrhı se refiere por primera vez a Barbastro como una madhına plenamente consolidada en el año 886-887. La ciudad debió adquirir un gran desarrollo a lo largo de la segunda mitad del siglo IX. Su importancia explica que en el año 918 Amrhus ibn Muhammad ordenara la construcción de un nuevo recinto de sillería, dotado de sus propios torreones, destinado a conceder todavía una mayor protección a esta ciudad, lo que demuestra el éxito de la fundación de Jalaf. Esta muralla fue considerada por al-Himyarhı como la más sólida de la Marca Superior.
Debió ser a lo largo del siglo X cuando el castillo asentado en la llamada Peña del Sepulcro fue transformado en una zuda (sudda), una alcazaba fortificada donde residía el gobernador de la plaza y del distrito.
La ciudad contaba con varios arrabales, baños y una gran mezquita aljama.
El reino cristiano de Aragón, surgido en el siglo XI, consiguió su primera gran victoria frente al Islam precisamente en 1064 con la toma de Barbastro por Sancho Ramírez. En la conquista participaron caballeros de toda Europa: el conde de Urgel, el duque de Aquitania, numerosos guerreros franceses y nobles venidos de Cataluña y Normandía. Se apoderaron del Arrabal y desde aquí asediaron la ciudad durante meses.
A la conquista de Barbastro se le ha denominado la "primera cruzada" pues fue el papa Alejandro II (1061-1073) el primero en transformar los derechos de San Pedro en guerra santa reconquistadora encomendada a la nobleza francesa, guerra que convertiría las nuevas zonas ocupadas en territorio vasallo de la Sede Apostólica. Así, el rey aragonés Sancho Ramírez, que necesitaba fortalecer su pequeño reino pirenaico frente a Navarra y frente a Castilla, se sometía a Roma para que garantizase su independencia y le reportase instrumentos ideológicos para su propio fortalecimiento político
La caída de Barbastro supuso una gran pérdida para el Islam, como reflejan las palabras llenas de sentimiento de Ibn Hayyhan (988-1076):
«En el año 456 [25 de diciembre de 1063 a 12 de diciembre de 1064] el enemigo se apoderó de Barbastro, la fortaleza más importante de Barbithaniyya, entre Lérida y Zaragoza, las dos columnas de la Frontera Superior. De Barbastro, esta madre venerable, donde el Islam había florecido después de la conquista de Mhusa ibn Nusayr, que durante siglos había gozado de una prosperidad continuada, que se glorificaba de su fértil territorio y de sus fuertes murallas, que construida sobre las riberas del Vero, era el baluarte de los habitantes de la Frontera contra los ataques de los enemigos; que durante trescientos sesenta y tres años había estado en poder de los musulmanes, de manera que la religión tenía allí profundas raíces y donde se estudiaba el Corán de una manera continuada. Este triste acontecimiento fue desde entonces el tema exclusivo de conversación, y todo el mundo se imaginaba que la misma Córdoba sería prontamente azotada por la misma suerte».
Sin embargo, el objetivo de aquella primera conquista de Barbastro no era tanto consolidar la conquista de un espacio más amplio dependiente de la ciudad musulmana, cuanto conseguir riquezas y esclavos. Por eso ocho meses después, un ejército musulmán dirigido por al-Muqtadir, rey de Zaragoza, reconquistó la ciudad a los cristianos. La combinación de la derrota aragonesa de Graus en 1063 y ésta de Barbastro dos años después, retrasaron un cuarto de siglo aquellos avances cristianos que tanto se habían hecho sentir en los años cincuenta del siglo XI.
