La seguente frase campeggia sullo stemma della città: “DAT MEGARA ORTUM HYBLAE LEO MARTEM ALVEARE MELILLI” (Megara dà a Ibla Melilli la nascita; il leone dà la forza e la prosperità). Melilli ha avuto una storia molto variegata dove la presenza dell'uomo è attestata fin dall'età del bronzo. La sua posizione strategica tra le maggiori città di Augusta e Siracusa ha svolto un ruolo cruciale per la sua crescita. Nel periodo feudale divenne dominio di Augusta e più tardi, della famiglia Moncada. Melilli è riuscita a sopravvivere a due devastanti terremoti nel 1542 e nel 1693. Dal 1842 detiene l'autonomia.
Melilli sorge nell'ex feudo Mezzamontagna sulle colline dei monti Iblei, digradanti verso il Mar Ionio e l'ampio golfo di Augusta. Il toponimo Melilli, ”sentiero trafficato”, è probabilmente di origine berbera (Malilah e Malili), dovuto alla posizione geografica occupata dal paese tra Catania e Siracusa. Il territorio di Melilli è stato abitato fin dalla preistoria: infatti sono molte le necropoli che testimoniano la presenza dell'uomo in questa parte della Sicilia. Il vasto territorio di Melilli, infatti, racchiude molte necropoli dell'età di Castelluccio (XVII – XV secolo a.C.), su cui gli archeologi hanno puntato i loro studi. La presenza di numerose necropoli rupestri fece affermare a numerosi storici e archeologi dei secoli scorsi che all'interno del territorio di Melilli fosse da ricercare l'antica Hybla sicula, il cui re Hyblon concesse ai megaresi dell'ecista Lamis la terra su cui fondare, nella seconda metà dell'VIII secolo a.C. Megara Hyblaea anche se gli archeologi identificano Hybla con Pantalica.
Nell'epoca bizantina, Melilli doveva essere un piccolo agglomerato rurale, che in seguito alle incursioni arabe e berbere, iniziate nell'827 d.C., richiamò per la sua naturale posizione fortificata gli abitanti dei villaggi circostanti, di cui restano ancora oggi tracce nelle varie contrade del territorio melillese. Certamente anche il piccolo agglomerato di Melilli dovette essere occupato successivamente da questi popoli che probabilmente diedero nuovo impulso economico ed edilizio al piccolo centro agricolo con la produzione del miele, la cui fama era già nota agli antichi greci e romani, e la produzione della canna da zucchero, arrivata in Sicilia probabilmente con le popolazioni berbere.
Sull'odierna cittadina, però, si hanno notizie storiche certe a partire dal XII secolo, quando il Casale di Melilli venne aggregato dal re Federico II di Svevia alla cittadina di demanio regio Augusta da lui stesso fondata. Durante il periodo feudale Melilli fu feudo di diversi principi e baroni fino al 1406 quando passò al regio demanio. Nel 1466 divenne baronia dei Moncada che la mantennero fino al 1812. Dopo due ricostruzioni in seguito ai devastanti terremoti del 1542 e del 1693 il reale decreto del 27 agosto 1842 elevò il Comune di Melilli a capoluogo di circondario di terza classe, con aggregato Villasmundo, fondato nel 1711 dal patrizio Consalvo Asmundo dei marchesi di San Giuliano.