Origini
Secondo la tradizione, Bitonto sarebbe stata fondata dal re illirico Botone, dal quale deriverebbe il nome. La presenza umana nel territorio risale all'epoca neolitica, testimoniata da insediamenti in grotte e da menhir. Una necropoli dell'età del ferro era situata presso un'ansa del torrente Tiflis, nella lama. Ciò fa presumere che la città fosse sede di una grande comunità che attirava la popolazione sparsa nelle campagne.
La città fu un importante centro peuceta, e dal VI secolo subì l'influenza delle città magnogreche, in particolar modo di Taranto. Dal III secolo a.C., quando la lega peuceta si sciolse, si dotò di una propria zecca, come dimostrano le stesse monete, rinvenute nel centro storico, che riportano l'immagine di una civetta con un ramo di olivo, altre una conchiglia, altre un granchio, altre ancora la testa di Atena. Il retro di queste monete riporta la legenda in caratteri greci "BYTON TINΩN" accompagnata in alcune dall'effigie dell'eroe tarantino Falanto, in altre da una spiga di grano, in altre ancora da un fulmine. Un'altra necropoli, risalente al IV-III secolo a.C., è stata inoltre rinvenuta nell'attuale centro urbano.
Periodo romano
In epoca romana fu municipio, mantenendo comunque il culto riservato alla dea Minerva, che veniva considerata dea protettrice non solo di Bitonto, ma di molte altre città apule e italiche. A lei veniva attribuito il dono dell'ulivo alla città. Un tempio a lei dedicato doveva collocarsi su uno sperone che domina il Tiflis, tra le attuali chiese di san Pietro in Vincoli e san Francesco la Scarpa. La presenza del tempio in quel periodo è confermata da una lastra di pietra cubica di epoca romana, riusata nelle mura della sacrestia dell'attuale chiesa.
La città era attraversata dalla via Traiana nel punto in cui il tracciato di quest'ultima si ramificava in due: la mulis vectabilis via per Peucetios citata da Strabone, che passava per Celiae, Azetium e Norba e la via Minucia Traiana, che passava per Barium. Le due vie, poi, si ricongiungevano a Egnazia. Fu stazione di sosta menzionata nell'Itinerarium burdigalense, nell'Itinerario antonino, nella cosmografia ravennate, nella tavola teodosiana, e nella Tavola Peutingeriana. Fu inoltre citata da Marco Valerio Marziale, da Sesto Giulio Frontino e da Plinio il Vecchio. Quest'ultimo fa riferimento solo al nome degli abitanti.
Medioevo
Dopo la dissoluzione dell'Impero Romano d'Occidente, del dominio di Odoacre e del regno gotico, gran parte della Puglia, inclusa Bitonto, fu riconquistata dall'impero Romano d'Oriente nell'ambito della "restitutio" giustinianea e si trovò coinvolta in una fase di lotte. La Puglia, come le altre regioni costiere italiane, infatti, era minacciata dalle scorrerie dei pirati saraceni. Al V-VI secolo risalgono i resti di una chiesa rinvenuti negli scavi sotto l'attuale concattedrale.
Successivamente, Bitonto fu nodo strategico nel sistema viario pugliese, centro gastaldale e roccaforte del thema di Longobardia. Nel 975 il catapano bizantino Zaccaria saccheggiò la città dopo aver sconfitto i Saraceni e ucciso il loro capo, Ismaele; nel 1010 Bitonto, Bari, Bitetto e Trani si ribellarono al governo bizantino dando inizio alla rivolta guidata da Melo contro gli stessi bizantini. Mesardonite fu mandato in Puglia per arginare la rivoluzione ma in uno scontro presso Bitonto avvenuto nel 1017 rimase ucciso. La rivolta si concluse con l'arrivo dei Normanni che posero fine in Puglia al dominio bizantino e agli attacchi dei Saraceni. Al 1089 risale la prima notizia certa dell'esistenza del vescovado bitontino. Nel 1098 Roberto, figlio di Guglielmo d'Altavilla, si proclamò dominator civitatis Botonti, instaurando una sorta di contea feudale.
Tra XI e XII secolo sotto il dominio dei Normanni di Ruggero II, Guglielmo il Malo e Guglielmo II, la città si rivestì di nuove mura. Il giudice bitontino Maggiore, a seguito della distruzione di Bari da parte di Guglielmo il Malo, assunse la suprema carica di regio giustiziere: grazie a lui e con l'aiuto dei Benedettini, prese il via la costruzione della nuova cattedrale. I Benedettini erano giunti in città in questo periodo, fondando fuori le mura l'abbazia dedicata a San Leone e dando un forte impulso all'economia cittadina, grazie anche alle nuove tecniche agricole e alla bonifica di nuove terre. La tradizionale "fiera di San Leone", che si svolge il 6 aprile per commemorare il Santo, si originò probabilmente proprio nell'XI secolo.
Con Federico II fu civitas specialis e rimase sempre nell'ambito del regio demanio, ossia alle dirette dipendenze della corona, escludendo il periodo feudale che va dal 1412 al 1551. Il 29 settembre 1227 inoltre, Bitonto fu teatro della scomunica, da parte di papa Gregorio IX, di Federico II accusato di essere sceso a patti con il sultano al-Malik al-Kamil.
Già nel Duecento iniziarono le dispute di confine con Bari per il possesso del porto di Santo Spirito, attraverso il quale si svolgevano i traffici marittimi. Nel 1265 il confine tra le due città venne fissato all'Arenarum, tra Palese-Macchie e Santo Spirito, ma il conflitto continuò ancora nei secoli successivi.
Agli Svevi subentrarono gli Angioini: Carlo I d'Angiò contribuì a formare in città una nuova nobiltà, composta soprattutto dai Rogadeo, Bove, Planelli e Labini, dedita ai traffici e al commercio. Tra i principali esponenti di quel tempo ci furono Sergio Bove e Giacomo Rogadeo, entrambi originari di Ravello, sulla costiera amalfitana. È questo un periodo di fioritura per la città, anche grazie a un'economia basata sull'esportazione di olio che continuerà a crescere fino al XVII secolo, quando si instaurò la dominazione spagnola. In Puglia, infatti, l'olio bitontino era apprezzato e richiesto soprattutto da Venezia.
Nel 1412 fu possesso feudale di Jacopo Caldora, duca di Bari e gran capitano dei soldati di ventura, che prese possesso della città nel 1434. Nel 1441 ebbe in feudo la città Giovanni da Ventimiglia, comandante generale delle armi regie di Alfonso I d'Aragona. Passò successivamente a Giovanni Antonio Orsini nel 1460, agli Acquaviva d'Aragona nel 1463 e, con l'ascesa al potere degli Spagnoli nel Mezzogiorno, il Re Carlo V di Spagna donò in feudo Bitonto nel 1507 al Gran Capitano spagnolo Consalvo di Cordova, conquistatore del Regno di Napoli e duca di Sessa.