Plus de quarante dolmens, sur les Causses Rouge et du Larzac, attestent de la présence de peuplades semi-nomades à l'âge du Bronze ancien (-2500 à -1500). Mais c'est à la Granède, sur un promontoire larzacien, qu'ont été découverts les premiers vestiges d'un village fortifié, datant du IXe ou VIIIe siècles avant notre ère. L'oppidum de la Granède, site de fouilles archéologiques, est le berceau de Millau.
L'agglomération va descendre dans la plaine alluviale de la Graufesenque à l'époque gallo-romaine. Du Ier au IIIe siècles après JC, un centre de production de vaisselle sigillée rassemble plus de 500 ateliers de potiers à la confluence du Tarn et de la Dourbie. Cet emplacement façonne le nom gaulois de la cité : Condatomagos, de condatos (confluent) et magos (marché). La cité s'étend peu à peu de la Graufesenque au Rajol, du Roc au Vivier, desservie par des voies romaines vers Rodez au nord, Nîmes et Narbonne au sud.

Du haut Moyen Âge, après le déclin de Condatomagos puis le passage des Goths, Vandales et Wisigoths en 407, il ne reste que peu de traces archéologiques. Les habitants ont-ils regagné l'oppidum ? L'agglomération s'est-elle dispersée en hameaux ? Entre temps, au Bas Empire, le nom de Condatomagos a cédé la place à Ameliavum, du nom d'une famille patricienne. Ameliavum deviendra Amilhau, puis Milhau, enfin Millau.