Die Gegend um Ostuni wurde seit der Altsteinzeit von Menschen bewohnt, wie Funde in der Grotta di Agnano innerhalb des Parco archeologico e naturalistico di Santa Maria D’Agnano belegen, die bis zu 30.0000 Jahre alte Kulthandlungen bezeugen.[1] Eine Siedlung wurde durch die Messapier gegründet und durch Hannibal zerstört. Von den Griechen wurde die Stadt wieder aufgebaut. Ihr Name rührt vom griechischen Wort Astu néon her (Neue Stadt). Nach dem Niedergang des römischen Reiches fiel die Stadt unter die Herrschaft des von Normannen beherrschten Lecce. In dieser Zeit begann die Entwicklung einer mittelalterlichen Stadt um dem 229 Meter hohen Gipfel. Auf dem Gipfel wurde eine Burg gebaut, von der nur noch Teile erhalten sind. Zudem entstanden die Stadtmauern mit 4 Toren. Von 1300 bis 1463 gehörte Ostuni zum Fürstentum Tarent und ab 1507 ging es in den Besitz von Isabella, Herzogin von Bari, über, der Frau von Gian Galeazzo Sforza, Herzog von Mailand.

Unter dem Einfluss von Isabella erlebte Ostuni einen Aufschwung im Zuge der italienischen Renaissance. Isabella hat in dieser Zeit Humanisten, Künstlern und Schriftstellern und auch Bischof Giovanni Bovio Schutz geboten. Isabella starb 1524 und Ostuni ging als Mitgift an ihre Tochter Bona Sforza, die zukünftige Frau von Sigismund I., König von Polen. Während der Regentschaft von Bona Sforza erlebte Ostuni eine freie und großherzige Führung. Bis 1539 errichtete sie Türme entlang der Küste als Schutz gegen die zu erwartenden Angriffe der Türken, die den Balkan kontrollierten. Die noch existierenden Türme waren stets besetzt und durch Leuchtfeuer miteinander verbunden.