I dati archeologici e documentari attestano che agli inizi del XIII secolo il sito dell'attuale città era deserto; il territorio era utilizzato per il pascolo o per la semina dagli abitanti dei paesi circostanti. Sparsi qua e là tuttavia vi erano insediamenti rupestri. È idea di molti autori invece che Altamura ha un'origine precedente molto antica anche se diverse sono le ipotesi su di essa. La fondazione della città è attribuita a Federico II di Svevia che passò di lì, nel 1228, percorrendo la via Appia per giungere a Brindisi e imbarcarsi alla conquista della Terra Santa. Il primo documento disponibile è il privilegio federiciano del 1232, col quale, l'Imperatore nominava un suo familiare Riccardo da Brindisi Arciprete della chiesa di Altamura. Altro atto ufficiale di nascita della "Terra" di Altamura è del 1243, dove si delimitava il territorio e l'assegnazione ai cosiddetti "revocati" e a coloro, che allettati dall'esenzione decennale dalle collette, vi si recarono spontaneamente.