En la 3-a jarcento a.K., la tiam nomita Rusadir estis parto de laKartaga Imperio. Post la falo de Kartago, la regiono venis subromia rego en 42 a.K., iĝante parto de la romia provinco deMaŭritanio Tingitana, konsiderita la Hispania Transfretana. Post la falo de la Okcident-Romia Imperio, la grandurbo venis sub la kontrolon de laVisigotoj, tiel iĝante parto de VisigotaHispania.[2] En la 6-a jarcento, en 534, la bizanca imperiestro Justiniano la 1-a konkeris Melilon kaj integrigis ĝin en laOrientromian imperion. Tamen, en 615, la urbo estis rekonkerita de la visigota reĝo Sisebuto. En 700, la islama armeo gvidita fare de Musa ibn Nusayr konkeris Rusadir, markante la komencon de la islama okupo de la regiono.
La situacio en Melilo restis relative stabila ĝis 1497, kiam la urbo, tiam forlasita pro konfliktoj kun la Sultanlando de Fes, estis okupita fare de Pedro de Estopiñán y Virués, nome de la Duko deMedina Sidonia kaj kun la subteno de laKatolikaj Gereĝoj. Tiu ĉi okupo markis la komencon de la hispana epoko en Melilo. En la 18-a jarcento, Melilo estis sieĝita fare de sultano Muhammad la 3-a inter 1774 kaj 1775. Tamen lasieĝo malsukcesis danke al la rezisto de la urbo, gvidata de la generalo komandanto Juan Sherlock, subtenata de la britoj, kiu aldonis internacian dimension al tiu ĉi epizodo.