The spread of domestic animals through time is one of the topics studied by archaeologists to assess human trade and migration. Here we present mitochondrial analysis of 42 archaeological cattle (Bos taurus) bone samples, from 16 different sites in the Iberian Peninsula and covering a broad timeframe (from the early Neolithic to the Middle Ages), to provide evidence about the origin and dispersion of the T1 cattle haplogroup in relation to human contacts and movements. The presence of the T1 haplotype in one sample from an early Neolithic site close to the Mediterranean coast of Iberia, and its continuing presence in the Peninsula during Roman and Medieval times, clearly demonstrates that T1 was not solely a Muslim or later introduction. Rather, our molecular data show evidence for a pioneer coastal colonisation of the Iberian Peninsula from the Mediterranean basin, followed by possible further colonisation, leading to a continuity of diversity through time.