Под основанием в этом контексте подразумевается не фактическое основание Мелильи берберцами, а завоевание города испанцами в 1497 году в ходе отвоевывания Тингитанской Мавретании — провинции Римской империи, которая занимала север современного Марокко и после распада Римской империи была завоевана мусульманскими племенами.
К началу VIII века арабы завоевали не только значительную часть Азии и северную Африку, но и практически весь Пиренейский полуостров. В ответ пиренейские христиане — в основном испанцы и португальцы — начали отвоевывать свои земли. Этот процесс получил название реконкисты. Завершилась реконкиста в 1492 году отвоевыванием Гранады и объединением большей части Испании под властью Изабеллы I Кастильской и Фердинанда II Арагонского.
После завершения реконкисты испанцы начали подумывать о завоевании земель в северной Африке. Выбор пал на Мелилью, но, согласно Алкасовашскому договору 1479 года, город находился в португальской зоне влияния. Однако в 1494 году король Португалии Жуан II в порядке исключения разрешил испанцам предпринять попытку завоевания Мелильи.
В сентябре 1497 года Педро Эстопиньян повел войска дона Хуана Альфонсо Переса де Гусмана, 3-го герцога Медина-Сидония, на завоевание Мелильи. Город сдался практически без боя 17 сентября; с тех пор герб Мелильи повторяет герб рода Медина-Сидония. Впоследствии мусульмане пытались отвоевать Мелилью в 1694–1696 и 1774–1775 гг., но потерпели неудачу. 14 марта 1995 года Мелилье была официально предоставлена автономия.
Годовщина завоевания испанцами имеет в Мелилье статус официального праздника, но на остальной территории Испании он отмечается. По случаю дня города в Мелилье проходят праздничные мероприятия. Однако некоторые жители города его не празднуют, так как поддерживают присоединение Мелильи к Марокко.