In de Romeinse tijd was Palla (Bonifacio) het zuidelijke eindpunt van de Romeinse weg die langs de oostkust van het eiland leidde naar Mariana (Lucciana) in het noorden.[1]

De stad werd volgens de legende gesticht door de Toscaanse markies Bonifatius in 828. Bonifacio was strategisch gelegen en gold als bijna oninneembaar. De stad kwam in 1092 in handen van Pisa en vanaf 1195 werd de stad Genuees. Het werd zo het eerste Genuese bolwerk op Corsica, een eeuw voor Genua het volledige eiland in bezit zou nemen. Er kwam een immigratie van Liguriërs op gang, die nog steeds merkbaar is in de taal gesproken in de streek. De Genuezen versterkten de stad met een kasteel en een twee kilometer langs stadsmuur en breidden de stad uit in een dambordpatroon. Bonifacio kreeg privilegies en werd een quasi zelfstandige republiek met het recht om zelf munten te slaan. In 1420 werd de stad vruchteloos belegerd door de troepen van Alfons V van Aragón. Daarna, in 1528, werd de stad getroffen door de pest. In 1553 viel de stad wel en werd ze ingenomen door een Frans-Turkse coalitie geleid door Sampiero Corso. De Fransen bezetten de stad en ze moderniseerden de stadsmuren met bastions. In 1559 werd Bonifacio door de Vrede van Cateau-Cambrésis weer Genuees. In de 18e eeuw werd Corsica Frans en onder Frans bestuur werd de kazerne Montlaur, begonnen door de Genuezen, afgewerkt.[2] De stad, die toen ongeveer 3000 inwoners telde[3], verloor veel van haar privilegies.

In de 19e eeuw kende Bonifacio een zekere welvaart door de tonijnvisserij, de landbouw (wijnbouw en olijfteelt) en de verwerking van landbouwproducten. Zo was er een fabriek van kurken en fabrieken waar pasta werd gemaakt. Bonifacio werd zwaar getroffen door de epidemie van de druifluis. In de 20e eeuw volgde een exodus van de bevolking naar de grote steden, onder andere naar Marseille. Enkel door haar vissershaven en het daar gelegerde garnizoen bleef de economie overeind.

Aan het einde van de 20e eeuw herleefde de economie dank zij het toerisme. Bonifacio werd een belangrijke haven voor de pleziervaart en voor cruiseschepen.[4]