Fernando I siguió la vía romana que unía Zaragoza con Valencia por Daroca y Teruel. En Valencia reinaba el débil Abd al-Malik ben Abd al Aziz al-Mansur (1061-1064), que sucedió a su padre Abd al-Aziz ibn Amir, en enero de 1061. Se casó con la hija del rey de Toledo Al-Ma'mún. Esto permitió que el rey de Toledo interviniese en los asuntos de Valencia y, casi como primera consecuencia, obligó al Al-mail a apoyarlo en la guerra que tuvo con el rey de Sevilla. Más tarde, después del desastre militar en Paterna contra las tropas leonesas, Ma'mun, finalmente, destronó al valenciano.
En la primavera de 1065 Fernando llegó a Valencia, puso sitio a la ciudad y los musulmanes ofrecieron gran resistencia. Dado que le era imposible tomarla por asalto, simuló una retirada, lejos de la ciudad retiró sus tropas a Paterna, 5 km al noroeste de Valencia, en la orilla izquierda del río Turia, zona de huerto donde había varios "Raal" o "Rahal", también llamada de "Rafol" (haciendo con vivienda, más adelante en la reconquista se llamaron alquerías) de torre árabe, perteneciente a la red de torres defensivas de la ciudad de Valencia como la Torre de Albal, la Torre de Espioca (Picassent), la Torre Plaza (Benifaió), todas del siglo XI —cinturón terminado en el siglo XIII por los almohades—. Allí esperó por los musulmanes.
Los árabes fueron en su persecución; Fernando I, desde la torre de Paterna, ordenó a sus anfitriones que esperasen por los valencianos. Hasta la llegada de estos, Fernando I atacó con sus tropas, consiguiendo un gran triunfo. Totalmente inconscientes, los valencianos sufrieron pérdidas muy altas, y su rey solo pudo regresar a la seguridad de las murallas de Valencia gracias a la velocidad de su caballo.
En ese mismo noviembre, el día 10, Al-Ma'mún puso a su hijo en la ley, enviándolo como gobernador a Cuenca o Chelva de, según diversas fuentes.
Toledo fue anexada a Valencia y acuñó moneda con el nombre de Mamún en la ciudad del Turia. Al morir Ma'amún, su nieto se declaró tributario de Alfonso VI de León, que incluía Valencia para los leoneses, pero el gobernador de Valencia Abu Bakr se declaró independiente de Toledo y León, y se alió con el rey de Zaragoza al-Muqtadir o señorío saraqustí sobre Valencia.
El poeta Abu Ishaq al-Tarasuni relató lo que ocurrió en estos términos: «Ellos colocaron una cota de hierro mientras usted usaba túnicas de seda cada vez más bonitas... que feos eran ellos y que bello era usted si no fuera por lo que sucedió en Paterna».
Después de la batalla, el cerco comenzó nuevamente, pero luego, Fernando se sintió enfermo y ordenó el regreso a León, donde murió el 27 de diciembre de aquel año.
Fue enterrado en el sepulcro de piedra del Panteón de Reyes de San Isidoro de León que había construido, junto con su padre, Sancho el Mayor, Rex et Pirinaeorum Tolosae, como dice el epitafio. Era el 27 de diciembre de 1065.
