Del proprio nome Bitetto ha quattro spiegazioni. La più sobria: Bitectum, una forma latina dell'epoca in cui il territorio agrario fu suddiviso in contrade — Babuctam, che oggi è Bavotta, Clausurae, che oggi è Chiusure, e appunto Bitectum; quella forma ricorre nei documenti ufficiali dal medioevo all'età moderna. La seconda: Vitetum, terra ricca di viti — e la vite sta sullo stemma comunale, e in dialetto la parola per vigneto, v'tet, somiglia molto al nome del paese, vetétte. La terza è la più parlante: Bis Tectum, due volte il tetto, cioè una città ricostruita due volte, oppure un secondo tetto per gli abitanti di Bari fuggiti qui dopo che i saraceni avevano distrutto la loro città. La quarta, forse greca, è Beth Hetium, il villaggio arido, e descriverebbe il posto com'era: piccoli raggruppamenti agricoli su un terreno privo di sorgenti e di acque stagnanti. Di una città, in età romana, non c'è traccia: ai tempi di Orazio Bitetto non esisteva ancora. Quello che si è trovato è più antico e singolare — due tombe monoblocco del quarto o terzo secolo avanti Cristo, intatte, con dentro ceramica greca, e nel maggio del 1993, mentre si scavavano le fondamenta di alcune case, un sarcofago monolitico coperto da una lastra di pietra, col defunto deposto in posizione fetale insieme a ciottolini, piattini e lucerne.
Bitetto prese forma come villaggio unico intorno a un cenobio che i monaci basiliani costruirono in contrada San Marco, fra qui e Bitritto. Quei conventi li volevano i bizantini, e per una ragione pratica: attraverso l'influenza religiosa e politica dei monaci sulle famiglie contadine riuscivano a controllare meglio il territorio. Quando Roberto il Guiscardo cacciò i bizantini da Bari, nel 1071, i basiliani se ne andarono, e il cenobio diventò lentamente un cumulo di pietre coperte d'erba. La diocesi del paese si data con due bolle papali: una del 1025 non nomina Bitetto fra le sedi suffraganee di Bari, una del 1089 sì — dunque fu istituita fra le due. Il primo vescovo di cui si conosce il nome, Raus, partecipò al terzo concilio lateranense; l'ultimo morì alla fine del Settecento, e nel 1818 la sede fu incorporata nell'arcidiocesi di Bari. Quello che ne resta è la chiesa, uno dei pezzi migliori del romanico pugliese, tirata su nel 1335: due leoni di pietra che reggono le colonne del portale centrale, una lunetta con il Cristo e i dodici apostoli, e scene del Nuovo Testamento lungo la cornice. E dentro quella chiesa sta la cosa per cui il paese è conosciuto: il corpo del beato Giacomo, frate laico francescano nato a Zara intorno all'anno millequattrocento e morto a Bitetto nel 1496, rimasto intatto nei secoli.