La storia della Basilica:
La leggenda narra che, nel 1414, gli augustanesi avessero trovato una pesante cassa con al suo interno un simulacro, a quanto pare perso da una nave di passaggio. Provarono a portarlo con sé verso Augusta, ma non ci riuscirono, perché il carico risultò troppo pesante. Dopo diversi tentativi, i melillesi riuscirono a portare con sé il simulacro, come se questo volesse andare proprio con loro.
I melillesi allora costruirono la prima chiesa per San Sebastiano, con la facciata rivolta verso nord, che fu però distrutta completamente dal terremoto del 1693, da cui solo il simulacro di San Sebastiano rimase intatto. Della primitiva costruzione edificata a poca distanza dal sito rupestre della Grotta della Carcarella, posta sul retro della chiesa attuale, sono pervenute solo le colonne facenti parte delle strutture della canonica della parrocchia.
Nel 1718 una parte delle strutture è realizzata da Girolamo Palazzotto.
Il 13 Dicembre 1990, col terremoto di Santa Lucia o terremoto di Carlentini del 1990 le strutture sono soggette ad interventi di manutenzione e di restauro.
La facciata della Chiesa
Il sagrato con motivi geometrico-floreali di alto pregio artistico è raccordato al piano stradale da due gradini in pietra, adiacente alle strutture ubicate sul lato destro, a ridosso dell'altura, ove prende avvio il monumentale Loggiato.
La chiesa si presenta con una monumentale facciata in stile barocco, divisa in tre parti. Su ognuna di queste parti campeggia la scritta: "TEMPLVM - SANCTI SEBASTIANI – MARTYRIS”. In alto possiamo trovare le tre campane della basilica. Un vero spettacolo.
Il portale principale reca una scena del martirio tramite frecce, mentre gli ingressi minori sono contraddistinti dalla presenza dei Simboli del martirio: frecce, palma (martirio) e corona (fedeltà).
Interno
Impianto a croce latina ripartito in tre navate per mezzo di pilastri, sette campate con archi a tutto sesto per lato, due absidiole laterali senza transetto. La volta della nave principale è abbellita con apparato pittorico realizzato tra il 1759 e il 1763 da Olivio Sozzi: Gloria di San Sebastiano e la Beata Vergine mediatrice di tutte le Grazie, due medaglioni raffiguranti il Trionfo della Fede e la Pace e la Giustizia, dipinti su tela applicati al legno del soffitto. Ai margini quattro dipinti a tempera raffiguranti le virtù cardinali: Prudenza, Giustizia, Fortezza e Temperanza. Le calotte di ogni singola cappella laterale sono ricoperte con dipinti a tempera raffiguranti le Virtù: navata sinistra le allegorie Fortezza, Verginità, Devozione, Misericordia, Purezza e Obbedienza. Navata destra: Umiltà, Grazia divina, Fede, Costrizione, Castità, Vittoria e Costanza.
Altare maggiore
La sopraelevazione dell'altare versus Deum è costituita da una coppia di colonne binate sormontate da capitelli corinzi a sostegno di timpani sovrapposti e spezzati, all'interno la raffigurazione dei simboli del martirio: Corona e Palme. Sulle cimase del timpano sono adagiate le due statue raffiguranti la Fede e la Fortezza. Sul paliotto della mensa la raffigurazione della Pia vedova Irene che medica San Sebastiano ferito, opera marmorea dello scultore palermitano Ignazio Marabitti.
Nell'edicola centrale è collocato il dipinto raffigurante il Martirio di San Sebastiano, copia dell'originale di Olivio Sozzi distrutto nel 1946, opera di Giovanni Valenti da Niscemi 1992. Il quadro cela la nicchia ove è riposta la statua del bimartire. Il venerato simulacro è svelato durante i due cicli di ricorrenze liturgiche.