Nel territorio di Valenzano sono state ritrovate diversi insediamenti funerari risalenti al IV secolo a.C., che testimoniano come l'area fosse abitata da popolazioni di stirpe peuceta. Originari dell'Illiria sulla costa est dell'Adriatico meridionale, i Peucezi si stanziarono nel territorio della Puglia centrale e tennero contatti commerciali con le colonie della Magna Grecia tra cui Taranto.
Dopo le guerre sannitiche, i romani assoggettarono la Puglia e l'attuale territorio di Valenzano fu probabilmente parte degli estesi latifondi che circondavano la città di Cælia (attuale Ceglie del Campo).
La definitiva fondazione dell'attuale paese è collocata intorno all'845 d.C., nello stesso periodo in cui i Saraceni giunsero a Bari distruggendola. Lo storico settecentesco P. Bonaventura da Lama ha congetturato la fondazione del villaggio ad opera di un nobile barese di origine bizantina, di nome Valenziano o Valentiniano, che si sarebbe accasato al sicuro dai Saraceni nei pressi di una chiesa rurale (probabilmente quella sulla quale fu, in seguito, edificata la chiesa di Santa Maria di San Luca).
Sempre P. Bonaventura da Lama ipotizzò che Valenzano, insieme a molti insediamenti circostanti, fosse distrutta per mano saracena alla fine del X secolo e verso la metà dell'XI. Nella prima occasione l'abitato sarebbe stato incendiato e una parte degli abitanti fatta prigioniera e condotta in Sicilia in schiavitù.
Con l'avvento del feudalesimo, Valenzano (denominata Ballenzanum) acquisì le caratteristiche di un feudo di media importanza. Il paese era dotato di mura ed aveva una forma pressoché quadrata, dal lato di circa 180 m. Le porte erano tre, quali la porta di via Bari, la porta di Santa Croce e la porta di Levante. Entro le mura vi erano numerose costruzioni, quali le carceri e le residenze del feudatario e dell'arciprete.
I proprietari del feudo di Valenzano noti furono:
- Nicolò De Cicala (1177)
- Elia Sclavo (1187)
- Iccerio De Mignach (1283)
- Nicolò Spinelli (1354)
- Moncello Arcamone (1382)
- Nicolò Fusco (1400)
- Famiglia Dottula (1417)
- Giacomo Caldora (1434)
- Famiglia Passarelli
- Famiglia Mangliabeto
- Famiglia Buci
- Famiglia Carafa (1470)
- Famiglia Furietti (1603)
- Famiglia Zevallos (1748)
- Famiglia Martucci (1806)
Il borgo rimase un feudo sino alle leggi eversive della feudalità, promulgate il 2 agosto 1806 da Giuseppe Bonaparte.
Durante la rivoluzione napoletana del 1799, l'intera Terra di Bari fu interessata dagli scontri fra i repubblicani, favorevoli al movimento rivoluzionario e all'abolizione della monarchia borbonica, e i sanfedisti contro-rivoluzionari. A Valenzano - come nei vicini centri di Carbonara, Ceglie, Triggiano e Loseto - prevalsero i secondi. La sollevazione sanfedista fu duramente contrastata dall'esercito dell'Impero Francese, che affrontò e sconfisse i ribelli.
Terminati gli scontri post-rivoluzione, Valenzano venne dapprima annessa al Regno delle Due Sicilie e successivamente nel 1861 al Regno d'Italia. Il paese, dovendo affrontare numerosi disagi economici come la maggior parte delle città del Meridione, fu colpito in primo piano dal fenomeno dell'emigrazione di massa a cavallo dei due secoli. In particolare, molti valenzanesi scelsero come meta d'emigrazione il Venezuela.
Nella seconda metà del XX secolo, Valenzano ha accresciuto i legami con la confinante città di Bari, ed è stata caratterizzata da un rapido incremento demografico e dalla dislocazione di numerosi servizi del capoluogo inclusi i centri di ricerca scientifica e tecnologica.
Origini del nome
- Nei documenti più antichi in cui viene citato, il paese viene chiamato Balentianum, Balenczanum, Balzano, il che può fare ipotizzare la derivazione del nome dalla radice indeoeuropea "balt", che significa palude, acquitrinio. La presenza nel territorio comunale dei letti di ben tre torrenti, il Montrone - Valenzano, La Fitta ed il Picone, rende plausibile l'ipotesi.
- Secondo un'ipotesi abbastanza accreditata il nome deriverebbe dal termine latino Valentianum, ovvero «proprietà di Valens», nome proprio latino diffuso nel Basso Impero.
- L'ipotesi riportata da Bonaventura da Lama, parlando dell'occupazione di Bari da parte dei Saraceni, attribuirebbe il nome Valenzano a quello del sopracitato fondatore greco del paese, il cui nome era, secondo lo storico, Valentiniano o Valenziano.
- Sempre Bonaventura riporta un'altra ipotesi, secondo la quale il nome del paese deriverebbe dalla sua favorevole posizione geografica. Al tempo della fondazione del borgo, il territorio sul quale sarebbe sorta Valenzano era infatti un'ampia campagna ben aerata, adatta perciò agli infermi: in latino, «quia valet insanus». Da valet insanus sarebbe derivato il nome Valenzanum.
- Un'ultima ipotesi fa derivare il nome del borgo da vallis sana, ovvero «valle libera» (l'aggettivo sanus, infatti, ha il secondo significato di "libera").