miniatura|derecha|Recintos fortificados de Melilla en 1849 La historia de Melilla comenzó en milenio a. C. el los fenicios se instalaron en un lugar que se llamó Rusadir, que significa en púnico "cabo imponente".
En el esta ciudad formaba parte del Imperio cartaginés. La región fue anexionada por el Imperio romano en el , siendo considerada como la Hispania Transfretana. Posteriormente, pasó a ser parte de la Hispania visigoda.
En el año 534 fue conquistada por el emperador bizantino Justiniano I. Fue recuperada por el visigodo Sisebuto en el 615. En el año 700 el musulmán Musa ibn Nusair conquistó Rusadir.
En 1497 Melilla, que se encontraba abandonada debido a un conflicto con el sultanato de Fez, fue ocupada por Pedro de Estopiñán y Virués, como comandante del duque de Medina Sidonia y con el apoyo de los Reyes Católicos.
Entre 1774 y 1775 la ciudad fue sitiada, sin éxito, por el sultán Mohammed III, con apoyo británico, siendo defendida por el comandante general Juan Sherlock.
Melilla ya aparece como plaza española en el Tratado de Paz de 1767. Los tratados de 1767, 1780 y 1785 son mencionados también en el Tratado de Paz de 1799. El territorio español de Melilla fue delimitado por el Tratado del 14 de noviembre de 1863.
Edad Antigua
Fenicios, griegos y cartagineses miniatura|derecha|Ánforas en el Museo de Melilla. El origen del poblamiento en el Cabo de Tres Forcas se debe a la colonización de los fenicios de Tiro en el El nombre Rusadir significa en púnico "cabo imponente" y perduraría durante los periodos púnico y romano y hasta principios del . A finales del el griego Hecateo de Mileto la llamó Metagonium, que tiene el mismo significado. En una obra geográfica griega del se llama a esta ciudad Akros y a la isla de Alborán Drinaupa.
El primer núcleo de población estuvo en Melilla la Vieja. En el es descrita como amurallada, aunque también debía de haber población extramuros. En el la población de Rusadir quedó bajo el control del Estado púnico. En el las tropas cartaginesas del general Amílcar Barca salieron de Cartago, pasaron por Rusadir y llegaron a Gadir, la actual Cádiz, para reforzar el control púnico del norte de África y de Iberia. La fundación de Cartago Nova, la actual Cartagena, hacia el por el general Asdrúbal dio más importancia a Rusadir. Aníbal Barca mandó 16 000 soldados de Iberia al norte de África, para defender Cartago, Rusadir y las ciudades de su entorno. De esta época datan los hallazgos de 1953 de monedas cartaginesas durante el dragado del puerto. En 1981, por un nuevo dragado en el puerto, se descubrieron madera, clavos y monedas, la mayor parte de las cuales eran cartaginesas, de un barco cartaginés hundido entre los años 220 y . Este barco transportaba la paga de unos mercenarios.
Las minas de plomo del monte Afra cerca de Melilla y actualmente en Beni Buifrur, fueron explotadas desde la Antigüedad. Se ha encontrado un ídolo de plomo de la diosa fenicia Astarté y otro del dios cartaginés Tanit realizados con plomo de estos yacimientos. En estas minas hay una gran estancia que recibe el nombre de Cámara del Elefante de Aníbal. Además de la minería del plomo, las civilizaciones que poblaron la zona en la Antigüedad explotaron el cobre, la plata y el oro.
Época romana A mediados del en época de la República Romana, la ciudad fue sitiada, sin éxito, por el general romano Cneo Pompeyo el Joven. Algunas monedas acuñadas en el en Rusadir muestran una espiga de trigo, lo que indica el cultivo de este cereal, y otras un racimo de vid, lo que indica también la producción de vino. También había olivares, para la producción de aceite. También se han encontrado monedas de Rusadir de esta época con una abeja, lo que indica la producción de miel y enlaza con el probable etimología de Melilla. Melilla también ha sido exportadora de perlas.
Tras el fin del Imperio cartaginés en las guerras púnicas, la región quedó bajo dominio del Reino de Mauritania. En el año , Boco II de Mauritania, muerto sin descendencia, legó su reino a Roma. En el año , Augusto le dejó el gobierno del territorio a Juba II, aunque siguió estando bajo control romano. Hacia el año , Ptolomeo, hijo de Juba II, pasó al trono mauritano. En el año , Calígula asesinó a Ptolomeo y se desató una revuelta en Mauritania, comandada por su liberto, Aedemón, que fue sofocada por las tropas romanas. En el año el emperador Claudio anexionó el reino de Mauritania al Imperio romano y lo dividió en dos provincias, la Mauritania Tingitana y la Mauritania Cesariense. Melilla se encontraba en la Mauritania Tingitana.
En el año el emperador Otón puso dentro del territorio de la Hispania Ulterior el otro lado del estrecho, la Mauritania Tingitana, como la Hispania Transfretana (España del otro lado del estrecho). Vespasiano dividió la Hispania Ulterior en Lusitania y Bética, quedando la Tingitana bajo la administración de la Bética. Con el gobierno de Adriano, pasaron a tener una administración propia la Bética y la Mauritania Tingitana. Caracalla nombró a esta última Nova Hispania Ulterior Tingitana. Con el gobierno de Diocleciano, entre 284 y 305, se organizó el Imperio en diócesis. En la diócesis de Hispania se incluyó la Mauritania Tingitana.
La ciudad fue mencionada en el por los geógrafos romanos Pomponio Mela y Plinio el Viejo, que mencionó también su puerto.
El romano Virgilio en el y Plinio el Viejo en el mencionan la producción de miel en el norte de África y la profesión de recolector de miel (mellarius) como una de las más rentables.
En el el emperador Claudio le dio el rango de municipium.
En el , el geógrafo e historiador griego Estrabón mencionó que Malaca, la actual Málaga, tenía relaciones comerciales con las ciudades mediterráneas del norte de África. Las ciudades norteafricanas también comerciaban con las peninsulares de Gades, Carteia, Cartago Nova y Cástulo.
El Cerro de San Lorenzo fue un lugar de enterramientos en la Antigüedad. Se descubrieron restos en la parte oriental en 1904 y 1913. En la parte oriental se descubrió una necrópolis púnica. El terreno fue usado también como necrópolis desde comienzos del . En la segunda mitad del se abandonó. Las tumbas de la parte oriental del cerro están cubiertas con ánforas, lo que no es habitual. En 1987 se descubrieron los enterramientos romanos de la parte occidental, de entre los siglos y . En este sitio las tumbas estaban cubiertas con las tégulas habituales. Entre 1915 y 1918 se descubrió otra necrópolis en el barrio de Santiago, que también tenía tumbas tapadas con ánforas. En 1914 se descubrió otra necrópolis en el barrio del Real y, en 1916, se descubrieron más enterramientos en ese barrio. Que hubiera tres necrópolis en sitios tan cercanos indica que ya era una ciudad con una gran población entre finales del y el .
Hubo una gran necrópolis de entre los siglos y entre el Parque Lobera y el barrio de Ataque Seco. Se han hallado restos en 1928, 1930 y 1962.
En el , Rusadir aparece en la obra Geografía de Claudio Ptolomeo. En el , en el Itinerario de Antonino, se mencionan las islas Alhucemas y Chafarinas y Rusadir (Melilla).
En esta región hubo presencia cristiana desde la época romana. En la parte occidental del Cerro de San Lorenzo se encontró una lucerna romana con símbolos cristianos. A mediados del Cipriano escribió una carta al obispo de la región, llamado Quintus. En 484, tras la época romana, consta que Rusadir tenía un obispo.
Época bizantina
Entre el 422 y el 429 los vándalos, con el rey Gunderico, se instalaron en la provincia Bética. En el 429, con el rey Genserico, los vándalos cruzaron el estrecho de Gibraltar, desembarcando en Tánger y Ceuta. Posteriormente, tomaron Volúbilis en su marcha hacia Cartago, donde instalaron su capital. Con el reino vándalo, Rusadir pasó una etapa de decadencia.
En el año 534 las tropas del emperador bizantino Justiniano I, comandadas por el general Belisario, conquistaron los territorios vándalos del norte de África, así como Menorca, Mallorca y las Pitiusas en Baleares.José Manuel Rodríguez Gómez-Escobar, Los visigodos: Hispania visigoda "9.- El reino visigodo de Toledo ", 2003.
En el 614 fue conquistada por el rey visigodo Sisebuto.
Edad Media
Califato omeya
El general omeya Amr ibn al-As ocupó Egipto en el 640 y Libia en el 643. En el año 700, el general Musa ibn Nusair conquistó Rusadir.
Banu Salih
A comienzos del el yemenita Salih I ibn Mansur construyó la ciudad de Ribat Nakur en un lugar conocido como Agdal, en la vega de los ríos Nakur y Gis. Se creó un emirato con capital en Ribat Nakur que controlaba desde Badis (Vélez de la Gomera) hasta el río Muluya. En el 709 el califa omeya Walid I le concedió este territorio. Este fue gobernado por la dinastía de los Banu Salih.
El nombre de Melilla parece tener su origen en el bereber Amlil, Malil y Mlil. Ese nombre tiene su origen a finales del . Según el historiador del Juan Antonio de Estrada los árabes la llamaban Milila. Según el historiador del León el Africano y según Juan Antonio de Estrada, el nombre se debe a la producción de miel.
Califato de Córdoba
En el 929 Abderramán III creó el califato omeya de Córdoba. Hacia el 931 Melilla pasó a depender de este califato. El califa nombró cadí de la ciudad al melillense malikí Abu Yáfar Áhmad Ibn Al-Fath Al-Malili. Al igual que en Ceuta, se realizaron obras públicas que mejoraron la ciudad. Las murallas fueron reconstruidas y se construyó una alcazaba interior. Según el historiador contemporáneo Áhmad al-Razi, en Ceuta y Melilla el urbanismo era perfecto. El historiador Ibn Hawqal, tras visitar Melilla hacia el 960, dijo que era una ciudad espaciosa y rica, con una muralla inexpugnable.
En el 955 Abderramán III situó en el puerto de Almería la base naval de la escuadra. Este puerto pasó a convertirse en el más importante de Al-Ándalus. De aquí salían rutas comerciales que pasaban por el norte de África y por el Bajo Guadalquivir. Había una ruta que llevaba directamente a Melilla.
Taifa de Melilla
En el estaba gobernada por la tribu bereber de los Beni Urtedi. El historiador Abdallah al-Bakri la describió como una ciudad antigua, con una muralla de piedra y con bazares. También decía que la urbe había sido reformada por los Banu Al-Bury Ibn Abi Al-Afiya Al-Meknasi.
Posteriormente, un descendiente del emir cordobés Al-Hákam I, Abd al-Aziz Ibn Áhmad Ibn Muhámmad Ibn Muhámmad Ibn Al-Asbag Ibn Al-Hákam Al-Rabadi, pasó a nombrarse gobernante de Melilla. En el 1063 los melillenses y habitantes de los alrededores lo expulsaron a Málaga y nombraron gobernante al hammudí Muhámmad Ibn Idrís Al-Mustali, que había sido emir de la taifa de Málaga hacia el 1054.
Imperio almorávide
Los almorávides surgieron tras una confederación de tribus nómadas saharianas, entre la que destacaban los bereberes lamtuna. Seguían la doctrina musulmana de Abdalá Ben Yasin. En el 1076 el emir almorávide Yúsuf ibn Tašufín realizó una campaña militar por el valle del río Muluya y conquistó Melilla.
Imperio almohade
En esta época se creó en el norte de África el movimiento de los almohades, basado en la doctrina islámica del mahdi Ibn Tumart. Entonces era gobernador Maksan Ibn Al-Mu'izz. En el 1142 el almohade Abd Al-Rahman Ibn Zaggu conquistó la ciudad, que fue devastada. En el 1204 el califa almohade Muhámmad an-Násir restauró las murallas.
Benimerines
En 1269 el sultán benimerín Abu Yúsuf Yaaqub conquistó Marrakech, lo que supuso el fin del Imperio almohade en el norte de África. Melilla fue conquistada por los benimerines hacia 1272.
Esta fue una etapa de decadencia para la región, ya que los benimerines tuvieron una política de impuestos excesivos al campo. En el tuvieron que sofocar algunas rebeliones.
El reino ziyánida de Tremecén reclamaba Melilla como propia y la devastaron en 1382.
Edad Moderna