Hay que enmarcar la fundación del monasterio de San Prudencio dentro de las tareas de reorganización del territorio una vez éste se recuperó del islam. El monasterio está situado en un lugar elevado en un valle que se abre al del río Leza. La tradición dice que el lugar donde se levanta el monasterio fue escogido de forma milagrosa ya que es donde se detuvo el caballo que llevaba el cuerpo de su patrón, San Prudencio. Inicialmente se construyó en ese lugar la iglesia de San Vicente. Alrededor del año 925 se reunió aquí una comunidad monástica de la que se conoce el nombre de su abad, Adica. El año 950 este abad encabezando su comunidad se entregó al monasterio de San Martín de Albelda, no lejos de este lugar, de donde pasó a depender. Posiblemente esta unión se hizo para proteger mejor la casa monástica levantada en un lugar de inestabilidad fronteriza.

Mientras el valle de Leza quedó bajo el señorío de Cameros en frente del cual se encontraba Fortún Ochoa, éste y sus descendientes se erigieron como protectores de San Prudencio desde el año 1058. Este hecho propició que la casa se beneficiara de las donaciones de sus señores y viviera una época de prosperidad, ya independiente de Albelda. Además los nuevos protectores de la casa impulsaron obras de construcción en el monasterio, además de erigir en ese lugar el panteón familiar. Los señores de Cameros fundaron en 1169 el monasterio cisterciense de Santa María de Rute, o Ruete, donde vertieron sus esfuerzos en detrimento de San Prudencio.