Ostunijev trg s stebrom svetega Oroncija

Regija okoli Ostunija je bila naseljena že od kamene dobe. Ppravljena izkopavanja so omogočila odkritje kosti in keramike. Vendar pa najbolj presenetljivo pričevanje ostaja odkritje okostja Gospa iz Ostunija, ženske, stare približno 20 let, ki je blizu poroda, in njenega ploda, ki ga je odkril prof. Donato Coppola z univerze Aldo Moro v Bariju leta 1991. Telo, postavljeno v veliko luknjo, je v skrčenem položaju, z glavo pokrito z nekakšno kapuco, sestavljena iz stotih majhnih školjk, najdena z desno roko, naslonjeno na trebuh, kot da bi zaščitila plod. Pripadnost ženske skupini lovcev potrjujejo ostanki kremena in zob primitivnega konja in vola. Pokop, imenovan Ostuni 1º, je edinstven na svetu: izpred približno 28.000 let (kalibrirano radiokarbonsko datiranje) je bil najden v jami Santa Maria di Agnano, v bližini istoimenske kmetije. Odlitek tega pokopa si lahko ogleda v "Muzeju predklasičnih civilizacij južne Murgije", v nekdanjem samostanu Monacelle, v zgodovinskem središču Ostunija.

Mesto naj bi prvotno ustanovili Mesapi, predklasično pleme, uničil ga je Hanibal med punskimi vojnami. Nato so ga ponovno zgradili Grki, ime Ostuni izhaja iz grškega Astu néon ("novo mesto").

Z razpadom Zahodnega rimskega cesarstva so Ostuni, tako kot ostalo Italijo, prečkali Ostrogoti, Langobardi, Saraceni in jih močno branila imperialna oblast, ki so jo izvajali Bizantinci. V bizantinski dobi je leta 876 nastala škofija in dala zatočišče bazilijanskim menihom iz Sirije in Egipta; ogroženih z arabsko ekspanzijo, predvsem pa z ikonoklazmom, so se menihi zatekli v iste jame, v katerih se je zatekal pračlovek.

Med 11. in 12. stoletjem so Normani osvojili bizantinska naselja v Apuliji in jih združili pod grofijo Apulija, ki jo je ustanovil Robert Guiscard, in nato postali vojvodina Apulija. Normani so okrepili tudi gojenje oljk in natančno določili meje mesta. V 12.stoletju je Goffredo III., grof Lecceja in uradnik sicilskega kralja Rogerija II., z vojaško jurisdikcijo nad Terra d'Otranto, zgradil grad na vrhu najvišjega hriba v Ostuniju; danes sta od te impozantne in dobro utrjene gradnje ostala le stolp in vrt (vrt Zurlo).

S Staufovci se je Ostuni precej razvil. Friderik II. Hohenstaufen je nameraval osvoboditi Ostuni njegovih fevdalnih vezi in mesto vzeti pod svojo neposredno in posebno zaščito tako, da bi njegov grad skupaj z gradom v Oriji, Tarantu in Brindisiju postavil za središče cesarske obrambe v Apuliji in ga oprostil davkov in uradnega nadzora. Poleg tega so morali prebivalci Villanove in Carovigna vzdrževati grad Ostuni, enega od Castra exempta Kraljevine Sicilije, pravzaprav je bil v 12. stoletju pristaniški sistem jadranskega območja pod oblastjo Ostunija. povečan z razvojem majhne Petrolle, danes Villa Novaa. Leta 1182 je Tancredi, grof Lecceja in gospodar Ostunija, podelil škofu in meščanom Ostunija, da ustanovijo središče blizu San Nicola di Petrolla in ga naselijo. Podelil mu je tudi mlin in peč, pri čemer si je pridržal pravico do sojenja.

Ostuni se je odprl za trgovino z Anžujci, ki so zgradili nove utrdbe za mesto in na ruševinah starodavne Petrolle ponovno ustanovili pristanišče Villanova (obalni del mesta). V aragonskem obdobju bil obdan z novim obzidjem s krožnimi stolpi: odprla so se štiri vrata, od katerih so danes ostala le Porta Nova iz 12. stoletja in obnovljena v 15. stoletju ter Porta San Demetrio iz 13. stoletja.

Med koncem 15. in prvim desetletjem 16. stoletja so se vodilni predstavniki judovske skupnosti Ostuni odlikovali v trgovini s tekstilnimi izdelki. Skupnost kot celota je bila ena najbolj uspešnih v deželi Otranto in ni bila izvzeta iz preganjanja s strani kristjanov.

Od leta 1300 do 1463 je bil del kneževine Taranto, od leta 1507 (skupaj z današnjim frazione Villanova in Grottaglie) je prešel na Izabelo Aragonsko, vojvodinjo iz Barija, ženo Giana Galeazza Sforze, milanskega vojvode. Pod Izabelino vladavino v času italijanske renesanse je Ostuni uspeval. Število prebivalcev je doseglo 17.000. Izabela je zaščitila humaniste ter ljudi umetnosti in slovstva, vključno s škofom Giovannijem Boviom. Umrla je leta 1524 in Ostuni je prešel kot dota na hčerko Boni Sforza, bodoči ženi poljskega kralja Sigismunda I.. V obdobju Bone Sforze je Ostuni še naprej užival stabilno vladavino. Leta 1539 je dala zgraditi stolpe ob vsej obali kot zaščito pred pričakovanimi napadi Turkov, ki so nadzorovali Balkan. Ti stolpi (še obstoječi, vključno s stolpi Pozzella, Pylon, Villanova in drugimi) so bili nameščeni in komunicirani z ognjenimi svetilniki.

Z Bourboni je mesto ponovno zacvetelo. Ostuni se je razširil proti bližnjim hribom Casale, Cappuccini, Sant'Antonio in Molino a Vento. Središče mestnega življenja se je s trga Piazza del Moro preselilo na današnji Piazza Libertà, kjer je danes mestna hiša (in nekoč sedež frančiškanskega samostana). Na tem trgu je Giuseppe Greco leta 1771 postavil steber v čast Sant'Oronzu, ki je po ljudskem izročilu mesto obvaroval pred kugo.

Na začetku 19. stoletja so na valu idealov razsvetljenstva Ostuni prekrižali tudi vstajniški nemiri: ustanovljena sta bila klub Giovine Italia in preprodaja Carbonara. Med temi vstaji je bil Ostuni prvo mesto v Apuliji, ki je postavilo trobojnico.

Od drugega povojnega obdobja do danes je ob razvoju kmetijstva in s tem povezane predelovalne industrije (oljčno olje, mandlji, vino) mesto postalo priznana turistična destinacija, ki je uspela nadgraditi svojo kulturno, zgodovinsko in arhitekturno. Na obali so nastale številne turistične vasice, kot je Rosa Marina, mednarodnega pomena, ena najčistejših na apulijski obali. Leta 2006 je bil na obali, ki meji na občino Fasano, ustanovljen Regionalni naravni park obalnih sipin od Torre Canne do Torre San Leonardo, zaščiteno območje velikega naravoslovnega in krajinskega poemna.