La zona di Bonifacio, abitata fin dalla preistoria, può vantare il privilegio di essere il luogo di ritrovamento della più antica donna della Corsica. Gli scavi compiuti ad Araguina-Sennola, all'entrata della città, hanno portato alla luce uno scheletro femminile denominato " La Dama di Bonifacio ", risalente al 6570 a.C. (preneolitico). Si tratta della più antica traccia di presenza umana in Corsica.

La località fu abitata anche ai tempi dei greci e dei romani; infatti, a qualche chilometro di distanza dalla città, vicino al Capo Sperone, durante alcuni scavi sono stati scoperti i muri abbattuti di una grande e splendida villa romana (Piantarella), testimonianza dell'esistenza di un importante centro di attività nel I° sec. d.C. Non lontano, lo stagno di Sperone, oggi insabbiato, fu nell'antichità un porto.

La storia della città, però, inizia solo nell'828, allorché Bonifacio, marchese della Toscana, diede il proprio nome alla borgata. Divenuta ben presto comune, per alcuni secoli essa visse di pirateria. Pisa e Genova miravano ad impossessarsi di questo porto naturale, punto nevralgico per il controllo del Mediterraneo occidentale, ma furono i genovesi ad infiltrarsi astutamente sul posto nel 1187 e a fondarvi, 8 anni dopo, una colonia. La città alla quale Genova aveva conferito numerosi privilegi, divenne una specie di repubblica autonoma, in grado persino di battere moneta e mantenne sempre un'assoluta fedeltà nei confronti della Superba.

L'importanza strategica del famoso promontorio roccioso, però, attirava i principali sovrani europei, che, in più occasioni, cinsero d'assedio la città, in particolare nel 1420 e nel 1553. Nel 1420, Alfonso V d'Aragona, basandosi su un atto del papa Bonifacio VIII, che aveva concesso la Corsica come feudo a suo padre Giacomo II, rivendicò il possesso dell'isola e per ben cinque mesi strinse d'assedio Bonifacio. I soldati aragonesi occuparono il porto, impedendo ogni rifornimento da terra; ne sbarrarono inoltre l'imboccatura con una massiccia catena di ferro, rendendo così vani i tentativi di aiuto esterno agli assediati. Nonostante le privazioni, i bonifacesi dimostrarono un coraggio eccezionale e, tra loro, le donne svolsero un ruolo di primo piano. Secondo la leggenda, i soldati spagnoli tagliarono sul fianco della scogliera Sud una scalinata di 187 gradini, per poter sferrare un attacco via mare agli assediati. In verità, questa scala " del Re d'Aragona " era stata realizzata precedentemente dagli abitanti di Bonifacio per poter accedere ad un pozzo. Grazie alla vigilanza di Margherita Bobbia, di guardia in quella occasione, l'attacco fallì. A questa coraggiosa donna, distintasi durante l'assedio per la sua prodezza, fu dedicata una via, ad Est della città. Alla fine, Genova riuscì a portare soccorso alla sua colonia ed Alfonso V d'Aragona fu costretto a togliere l'assedio.

Nel 1553, 25 anni dopo la grande epidemia di peste (1528) che uccise i due terzi della popolazione, la città dovette subire un nuovo assedio; fu, infatti, la volta del re di Francia Enrico II, le cui truppe, appoggiate dalla flotta del corsaro turco Dragut, per ben 18 giorni e 18 notti presero a cannonate la città. All'alba dell'ultimo giorno, i bonifacesi dovettero respingere tre attacchi consecutivi. Tutta la popolazione, compresi clero, donne e bambini, partecipò al combattimento con una tale determinazione da indurre quasi Dragut a levare l'assedio. Tuttavia il corsaro riuscì a sconfiggere gli assediati e a vendicarsi solo grazie ad un ignobile inganno. Domenico Cattaciolo, di ritorno da Genova con 15.000 scudi destinati a sostenere l'assedio, fu catturato da Dragut e presto si convinse a aderire alla causa franco-turca. Si presentò ai suoi concittadini con una lettera fallace in cui Genova confessava la propria incapacità di prestare loro soccorso. I bonifacesi si rassegnarono allora ad arrendersi in cambio di aver salva la vita ed i beni. Ma, non appena furono aperte le porte della città, il corsaro, contravvenendo alla parola data, iniziò un feroce saccheggio e massacrò la guarnigione nonché alcuni civili. Furono necessari l'intervento di Sampiero Corso, fautore peraltro della fatale alleanza franco-turca, ed il denaro del maresciallo de Thermes per indurre Dragut a risparmiare Bonifacio e ad andarsene.

Nel XIX sec., avveniva abbastanza frequentemente che un bandito corso, ricercato dalla giustizia, passasse le Bocche di Bonifacio e si rifugiasse in Sardegna; uguale viaggio, in senso inverso, veniva peraltro compiuto dai banditi sardi. Spesso si verificava anche che costoro facessero ritorno sulla propria isola solo per commettere un nuovo crimine e poi ripartire, ancora una volta sfuggendo alla legge. Questo traffico divenne talmente frequente da indurre le autorità dei due paesi nel 1819 e nel 1843, a concordare l'estradizione dei rispettivi fuorilegge e la sorveglianza delle Bocche di Bonifacio con navi militari. Bonifacio possiede la caratteristica particolare di aver conservato nel tempo una propria lingua, " il bonifacese ", di antichissima origine genovese, ancora oggi parlata da alcune centinaia di abitanti.