La storia di capo d'orlando ha inizio quando nel 1218 a.C. un dei sei figli di Eolo "Agathirnos" fa edificare sulle colline dell'attuale frazione di S. Martino l'antica citta di <Agatirno>. Il suo fondatore cinse la citta' di potenti mura e la rese prosperosa nel commercio. Dalle poche notizie storiche pervenute si e' certi che Agatirno avesse un grande porto, uno stabilimento balneare, nonche' una bellissima piazza nella quale affluiva l'acqua proveniente dalla sorgente di S. Domenica. Circa l'esatta ubicazione della citta', si ritiene fosse collocata presso l'attuale campo do S. Martino, dove affiorano tutt'oggi delle rovine. Importanti ritrovamenti che confermano l'esistenza della citta sono: la scoperta nel 1889, durante degli scavi, presso l'attuale villa cangemi di una lapide di marmo, delle anfore, il braccio di una statua e vario materiale; Nel dicembre 1980 e nel 1989 in pieno centro urbano furono ritrovate, durante l'esecuzione di scavi per la costruzione di nuovi edifici, i resti di una necropoli datata IV - V sec. a.C.
Ed ancora, nel 1987, vennero alla luce le terme romane, databili al III - IV sec. a.C.
Da queste scoperte archeologiche si confermano i pochi cenni storici pervenuti sulla citta' di Agatirno. Il vuoto di notizie storiche sulla citta' di Capo d'Orlando ha fine intorno al XII sec. sotto il dominio dei Normanni in Sicilia. Infatti, il geografo arabo Ibn Idris individuò nel luogo la Piccola Cefalù e descrisse la pianura come spiaggia ridente per l'a ricchezza e lertilita' del suolo. Nello stesso periodo i monaci Basiliani cominciarono ad edificare nelle loro terre site lungo la pianura le prime chiese, ormai non più esistenti, quali: S. Elia, S. Filadelfo, S. Filippo, S. Agata e S. Eustachio. Intorno a queste ultime si svilupparono i primi insediamenti di contadini. Nel XIV sec. si cominciò ad affermare la coltura delle cannamele nelle terre di Malvicino. Queste erano di proprietà dei Baroni di Naso che perciò eressero, a loro difesa, una torre con annesse opere fortilizie ed un trappeto per l'estrazione dello zucchero. Contemporaneamente si sviluppò anche la coltivazione dei gelsi con produzione di seta locale che veniva esportata in tutta la penisola. Sulla sommità del promontorio rimase in piedi fino al 1400 l'antico Castello, distrutto dopo una lunga battaglia tra le truppe Regie e gli Aragona - Baroni di Naso - che si erano ribellati al Re Martino.
La presenza del Castello, il porto ad esso sottostante ed i vari approdi lungo il litorale di S. Gregorio fanno presumere l'esistenza di nuclei abitati sia alle pendici  del promontorio stesso, sia a S. Gregorio dove, in particolare, è certa la presenza di molti fondachi per difendere i quali era stata eretta un'altra torre di difesa detta dei Quadaranini. Nei 1360 i Basilianì edificarono un nuovo Monastero intitolato a S. Maria de' Lacu nei pressi del Castello dì Malvicino, verso oriente, sulla cui localizzazione, ultimamente, sono emersi indizi più concreti. Nel 1488 venne impiantata una tonnara che interessò il lungo tratto di mare compreso tra Capo d'Orlando e Capo Calavà con le attrezzature a terra ubicate proprio a S. Gregorio. Nel 1600 si edificò il Santuario di Maria SS. di Capo d'Orlando sopra i ruderi dell'antico Castello; ciò a seguito di fatti miracolosi legati alla figura di S. Cono di Naso. Il 22 ottobre 1600, alla presenza delle autorita' civili ed ecclesiastiche venne solonnemente inaugurato il santuario dedicato a Maria SS. All'inizio dell'800 la tradizionale coltivazione del gelso fu sostituitadall'agrumeto, in pianura, e dall'uliveto sulle colline. Nella seconda metà del secolo XIX le ricche famiglie del vicino centro di Naso (a cui il territorio di Capo d'Orlando era annesso) cominciarono ad abitare le loro ricche terre della marina costruendovi delle belle dimore, imponenti all'esterno e finemente decorate, con pitture stucchi, all'interno. Queste abitazioni venivano, prevalentemente, abitate nel periodo estivo e durante il tempo di raccolta dei prodotti della campagna. Il loro sito, la tipologia, l'insieme del complesso architettonico venivano sempre scelti con molta cura, badando acche' la costruzione si modellasse all'intorno ambientale e, contemporaneamente, si contrappuntasse ad esso senza, per altro, alterare il ritmato equilibrio fisico del circostante territorio.Intanto il territorio orlandino venne ad essere segnato dai nuovi vettori dello sviluppo moderno costituiti dalle strade statali 113, e dalla linea ferroviaria. Le nuove vie di comunicazione fecero di Capo d'Orlando il polo d'attrazione del vasto hinterland nebroideo che su di esso gravita e ciò determinò la crescita della popolazione, prevalentemente impiegata nella coltivazione dell'agrumeto, e, conseguentemente, la crescita delle domande di nuovi alloggi che comportarono l'ampliamento del tessuto urbano. Da tali premesse nacque la lotta con Naso per l'Autonomia Comunale. Emblematico a proposito l'occupazione del terreno in contrada S. Martino per la localizzazione del nuovo cimitero: la popolazione orlandina il 12-9-1922, esasperata, vi seppellì il primo morto, il Sig. Francesco Paparone, il quale in vita aveva espresso tale desiderio: la salma venne regolarmente piantonata per alcune settimane onde impedire l'intervento delle Autorità Municipali di Naso. Fu così, con una serie di manifestazioni popolari pacifiche, che con Legge 25 Giugno 1925 N. 1170 venne concessa l'Autonomia Comunale; ed il 27 Settembre 1925 con l'ambito intervento di S. E. Giovanni Giuriati, allora Ministro dei LL.PP. in rappresentanza del Governo Nazionale, fu solennemente inaugurato il nuovo Comune.