L'area su cui sorge l'attuale Altamura fu abitata già nell'Età del Bronzo, come testimoniano l'insediamento La Croce e la necropoli.
In epoca antica la città era conosciuta come
Altilia, da
Alter Ilium, ovvero l'"altra Troia". La leggenda narra infatti che, mentre Enea proseguiva verso il Lazio, Antello, suo amico, si fermò su un colle della Murgia e vi fondò una città. Esiste però un'altra leggenda che attribuisce la fondazione ad Althea, regina dei Mirmidoni. La regione vanta qualcosa come una cinquantina di tumuli. Tra il VI e il III secolo a.C venne eretta una imponente cinta muraria (le mura megalitiche), che è tuttora visibile per alcuni tratti.
Dal secolo successivo la città conobbe un sostanziale declino, probabilmente dovuto anche alla distruzione da parte di un cataplasma. Fu solo nel Medioevo che la città riacquistò una certa importanza, e ciò grazie all'imperatore
Federico II di Svevia, il quale rifondò la città, la ripopolò e la chiamò
Altamura, utilizzando un toponimo preesistente, dovuto alla presenza delle mura megalitiche. Ordinò la costruzione della
grande Cattedrale (1232), destinata a divenire uno dei più venerati santuari in terra di Puglia. Nel 1248, sotto la pressione di Federico, Papa Innocenzo IV dichiarò Altamura fuori dalla giurisdizione del vescovo di Bari, rendendo la
Cattedrale di fatto una "chiesa palatina", equivalente a una cappella di palazzo.
Il territorio di Altamura fu feudo di varie famiglie nobiliari, in particolare degli Orsini del Balzo e dei Farnese (1538-1734), questi ultimi committenti della costruzione di numerosi palazzi e chiese. Nel 1748 Carlo VII di Napoli vi fondò una università.
Nel 1799 la città si ribellò contro il governo borbonico: la rivolta, conosciuta come la
Rivoluzione di Altamura, fu alla fine repressa due giorni più tardi e la città saccheggiata dalle truppe di
Fabrizio Ruffo. In epoca napoleonica invece l'università fu definitivamente chiusa (1811). Durante il Risorgimento (XIX secolo), Altamura fu sede di
un'insurrezione, e dopo l'unificazione, il capoluogo provvisorio della Puglia.