La zona de Mélida ha estado habitada desde la época prehistórica, ya que en su término municipal y en los alrededores se han localizado una serie de yacimientos arqueológicos. Durante la época romana, la gran importancia que tuvo la villa de Cara, hizo florecer la región, que se vió poblada por “villae” (granjas residenciales), como las de El Carrizo y El Coscojal. Esta última debió ser grande, ya que contaba en el siglo I d.C. con un horno propio para fabricación de cerámica.
Tras la conquista de los musulmanes de España (711) y su instalación en el valle del Ebro, la zona de Mélida se convirtió en tierra fronteriza entre el reino de Pamplona y los dominios musulmanes. Es decir, se trataba de lo que se denomina “tierra de nadie”, ya que nunca fue efectivo el dominio musulmán en la zona. No sería hasta el reinado de Sancho Ramírez (1076-1094) cuando la zona fue incorporada al Reino de Navarra.
A partir de estos momentos Mélida pasó a ser un señorío real, en el que el monarca cobraba rentas y calonias (multas que se pagaban por delitos de alteración del orden público) y ejercía jurisdicción sobre los labradores. Asimismo, el Rey se encargaba del mantenimiento del castillo, cuya construcción se sitúa a comienzos del siglo XIII, durante el reinado de Sancho VII el Fuerte. Asimismo, era el monarca quien nombraba al alcaide del castillo y se hacía cargo de la provisión de las guarniciones necesarias en caso de guerra. Finalmente, el rey Teobaldo II organizó el sistema tributario de los vecinos de Mélida, concediéndoles el 5 de noviembre de 1266 un fuero, en el que cedía a los labradores sus bienes y derechos en la villa, salvo el castillo y las calonias, a cambio de 200 cahices de trigo y 200 sueldos sanchetes de pecha anual.
Esta situación de realengo o dominio real se mantuvo hasta 1307, año en el que el rey navarro Luis Hutín cedió al noble Oger de Mauleón la villa de Mélida junto con otras propiedades, a cambio del castillo de Mauleón y diversas villas en el vizcondado de Soule en Ultrapuertos. Las condiciones impuestas por el monarca fueron el seguir manteniendo en su poder el ejercicio de la alta justicia y el resort, así como la obligación de no enajenar o vender nada de lo cedido, sino a personas sujetas a los reyes de Francia y Navarra. De este modo, pasó de ser un dominio real a tener titularidad señorial. Asimismo, varias tierras y propiedades de Mélida estaban en manos de familias nobiliarias como los Aibar y Cascante.