La peña de Deyo, hoy Monjardín, estaba coronada por un castillo-fortaleza edificado sobre la roca viva. Era una edificación vascona que se perdió en las primeras guerras contra los musulmanes. Tras distintos sucesos políticos y militares la fortaleza pasó a manos de la familia Muza, e Ismael, rey de Tudela y nieto de Muza, la entregó a Abd Allah como pago por su libertad.
El castillo suponía una barrera que cerraba el paso hacia la llanura que se extiende desde la cuenca del Ega hasta el Ebro. Era prácticamente inaccesible a través de las rampas rocosas de la ladera Norte, pero se podía llegar a él por el Oeste. Por este lado, la cuesta que conduce hasta la cumbre amplia y larga es más lenta, y en este punto, los musulmanes habían separado los muros de la fortificación de la explanada a través de un profundo foso cortado de lado a lado. En el interior del fuerte se encontraba la guarnición, y un pozo, probablemente de construcción romana, proporcionaba agua de forma permanente.
El ejército del rey Sancho I Garcés se dispuso a recuperar la plaza. Según Moret, el monarca visitó previamente el monasterio de Irache, situado a los pies de Montejurra, para encomendar la toma de la fortaleza a la Virgen. Los hombres de Sancho Garcés llegaron al castillo por el lado occidental y saltaron sobre el foso. Los tiradores asaetearon a los defensores que se atrevían a asomarse al exterior. El ejército pamplonés arrinconó a los defensones en su interior y éstos acabaron por rendirse y entregar la fortaleza.
Tras la victoria, el rey Sancho cumplió su promesa e hizo donación a perpetuo, al monasterio de Irache y sus monjes de la regla de San Benito, del castillo de Deyo y de los pueblos del valle de San Esteban. Desde este triunfo Sancho añadió al título de rey de Pamplona, "el de Deyo".