Paterna aparece en las crónicas cuando se reconquista en 1.213 por parte de Alfonso VIII, junto con los castillos de Alcaraz y de Riópar. Se sitúa dentro del Alfoz de Alcaraz y hasta fines del siglo XV fueron frecuentes las correrías de los moros por los pueblos de estas sierras por la continúa rebeldía del reino de Murcia frente a la corona de Castilla. Paterna tiene en el siglo XVI, 79 vecinos pecheros (que pagaban impuestos), un hidalgo y un clérigo. En el siglo XVII pasa a contar con unos 100 vecinos (413 almas).

Para concluir, a modo de ejemplo de lo antiguo del asentamiento de Paterna y de su humildad, sirva un apunte de las Relaciones o Descripciones de Lorenzana, Cardenal que fue de Toledo a finales del siglo XVIII: -"Se ignora por quien se fundó este lugar. No tiene armas algunas, ni historia de suzesos y no hay sujeto ilustre que aia tenido este pueblo más que el señor ilustrísimo don Pedro Benedicto, cura que fue de él, y al presente se halla obispo de Mallorca. No tiene edificios ni castillos fuertes, sólo se conservan algunas ruinas de un castillo que pareze sirvió de atalaya". (Paterna y abril 28 de 1.782. Don Antonio Gil)