Leggende hanno attributo la fondazione di Melissa a Melisseo Re di Creta, alla fama della maga Melissa, altri fanno derivare il nome "melissa" dal greco, miele, ape. Quest'ultima tesi fu preferita dai melissesi che adottarono  nello stemma del paese le api svolazzanti accarezzate con la mano destra dalla ninfa boschereccia.
Secondo alcuni studiosi invece la fondazione di Melissa sarebbe avvenuta nell'VIII secolo da un gruppo di contadini greci attirati dai terreni fertili, e poi sepolta da uno smottamento delle colline dovuto ad una alluvione. Il paese successivamente venne edificato su una collina rocciosa.
Dal  XIII secolo a  Melissa si sono succedute diverse signorie, fu anche sotto il dominio regio del Re Alfonso d'Aragona e del Re Ferdinando. Quest'ultimo vendette nel 1485 Melissa e il suo castello per 3000 ducati al tesoriere di  Calabria Vinceslao Campitello che sarà feudatario a Melissa con la sua famiglia fino al 1668, anno in cui passò alla famiglia Pignatelli.
Ancora oggi si possono osservare nel centro storico tratti significativi dell'antico borgo feudale, parti di cinta muraria. Il vecchio castello costruito in epoca medievale è andato distrutto dal tempo e dalla non curanza, si nota però ancora una delle torri che si innalzavano al dominio del paese. Anticamente esistevano tre porte di accesso al paese, oggi non visibili ma chiare nei ricordi degli abitanti, "Porta di chiusi, Porta di garda e Porticella" sorvegliate nel seicento dalle guardie del conte di Melissa.
Tra le chiese storiche ricordiamo quelle di San Giacomo e della Madonna dell'Udienza, la prima fatta costruire nel XVI secolo dal 2° barone di Melissa Lorenzo Campitelli, il quale aveva lo iuspatronato sulla chiesa. Raccontano i melissesi  che la  chiesa era collegata al castello da un cunicolo stretto e buio, attraverso il quale il conte si recava in chiesa per prelevare una sposa ed  esercitare lo ius primae noctis. All'interno della chiesa è custodita la lapide del conte di Melissa e principe di Strongoli Francesco Campitelli, ucciso dai melissesi per vendicarsi del ripristino dello "ius primae noctis". Era presente una volta anche il busto che venne distrutto e reso osceno dal popolo. Sul portale della chiesa è ancora visibile lo stemma della famiglia Campitelli, uno scudo tagliato in obliquo da una striscia che lo divide in due parti, in quella superiore è  raffigurato un leone, in quella sottostante tre rose a cinque petali. La chiesa dell'Udienza, invece, fu fatta costruire intorno al 1560, a imitazione dei Campitelli, da Domenico Pignatelli, situata fuori dall'abitato conserva sul portale lo stemma dei Pignatelli, un rastrello tridente e tre pignate, è interessante far notare un altare centrale ad intarsio costruito nel 1700 da un artigiano di Carfizzi. Altre chiese di Melissa, quella del patrono San Nicola di Bari e di San Francesco da Paola, quest'ultimo festeggiato nella prima settimana di  agosto con una grande processione e una sentita  partecipazione di tutto il popolo.
Interessanti sono i resti del Convento di S.Agostino (Località S.Maria delle Grazie, da dove è possibile osservare un bel panorama) sorto nelle campagne fuori dalle mura del paese nel 1546, e soppresso agli inizi dell'ottocento dai francesi.
Il territorio di Melissa si estende sul mare dove troviamo la frazione Torre Melissa, con la sua Torre Aragonese(vedi foto) che fu costruita per difesa dall'attacco dei turchi intorno alla metà del XV, utilizzata anche come residenza estiva dei conti di Melissa e dei familiari. Torre Melissa oggi è un interessante centro balneare, con ristoranti eccellenti, residence, camping, un mare pulito e soprattutto popolato da gente accogliente.