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.

Tras ser primero un dominio real y posteriormente señorial, Mélida se convirtió en un señorío eclesiástico a mediados del siglo XIV. Desde finales del siglo XIII y durante toda la primera mitad del XIV, las tierras y propiedades de la villa de Mélida fueron objeto de varias transacciones por las cuales pasarían de las manos de familias nobiliarias a formar parte del dominio del Monasterio de La Oliva, terminando finalmente por ser la villa, a mitad del siglo XIV, señorío del Monasterio. Sus primeros intereses patrimoniales en la villa se remontan al año 1281, fecha en la que el noble don Jimeno de Aibar mediante donación legó al monasterio la cuarta parte de todas sus propiedades, tierras, derechos y prestaciones que tenía en la villa de Mélida. A partir de esta donación, los monjes de La Oliva no perdieron la oportunidad de ir engrosando su patrimonio territorial y jurisdiccional, aunque no sin problemas. Además de por donación, el Monasterio de La Oliva consiguió propiedades en Mélida mediante compra y mediante permuta o cambio de bienes.

Durante la segunda mitad del siglo XIV, Mélida se vio afectada por las pestes de los años 1348 y 1362 y especialmente por la guerra contra Castilla de 1378, durante la cual las tropas castellanas al mando de Pedro Manrique destruyeron el castillo y provocaron que la villa quedara completamente desierta. Sin embargo, fue repoblada por cuatro o cinco antiguos vecinos a los que el Rey perdonó 10 libras y 5 sueldos que debía la población de Mélida en concepto de Cuarteles.

De nuevo, y ya a mediados del siglo XV, volvió a verse inmersa en otra guerra. En este caso se trata de la guerra civil que asoló Navarra durante esta época, en la que se enfrentaron los agramonteses, partidarios del rey Juan II, con los beaumonteses, defensores de Carlos, Príncipe de Viana. Mélida se alineó con el bando que resultaría perdedor, el del Príncipe de Viana que ganó para su causa entre otros el castillo de Mélida, que había sido reconstruido. Sin embargo, en el año 1455 el jefe agramontés Martín de Peralta asedió y tomó la villa, destruyéndose de nuevo la fortificación. Otro acontecimiento de esta guerra civil tuvo lugar en las cercanías de Mélida. Se trata de la muerte del Mariscal de Navarra, don Felipe, a manos del conde de Lerín.

Durante el reinado de los últimos reyes de Navarra, Juan de Albret y Catalina de Foix, los vecinos de Mélida disfrutaron de una serie de derechos en las Bardenas Reales como consecuencia de una concesión que otorgaron los monarcas al municipio en 1498 a través del gobernador del Reino, don Francisco Robray. Con anterioridad los vecinos disfrutaban de estos derechos, pero en esta fecha los reyes ratificaron como privilegios estas antiguas costumbres.

Como consecuencia de la conquista de Navarra por parte de las tropas castellanas, el rey Fernando el Católico ordenó derribar los restos que quedaban del castillo, demolición que fue llevada a cabo por el cantero Juan de Larrea, asistido por el capitán Guerrero. Tras la incorporación de Navarra a Castilla, Mélida continuó siendo un señorío eclesiástico del Monasterio de La Oliva, situación en la que continuó hasta la llegada del liberalismo en el primer tercio del siglo XIX.

A mediados del siglo XIX la villa de Mélida estaba formado por unas cien casas que se concentraban en un casco urbano formado por 6 calles y una plaza. Contaba con Casa Consistorial con cárcel, escuela de primaria, molino de aceite, molino harinero, tres fábricas de aguardiente y tres tiendas de comestibles y telas ordinarias. Estaba comunicada con los pueblos limítrofes mediante tres caminos que estaban en buen estado, uno que conducía a Carcastillo, otro a Caparroso y otro a Arguedas que atravesaba las Bardenas y que contaba con una venta. Asimismo, se recibía el correo de la estafeta de Caparroso por valijero. La población en esta época rondaba los 600 habitantes, número que fue aumentando progresivamente, en especial durante la primera mitad del siglo XX, llegando hasta los 1.300 habitantes, momento en que empezó a descender como consecuencia de la emigración hacia las ciudades.